Description:Parallel Search of 3x+1 Class Records
Abstract:The application implements a parallel search algorithm of delay Class Records (CR) over 3x+1 trajectories. Known optimization techniques of the basic algorithm are supplemented with novel ones. These, and especially the higher performance enabled by the 64-bit architecture of the machines running in the Cometa Grid Infrastructure, outperform current implementations on 32-bit machines by a rough 5 speed-up factor.
The most novel aspect of this application relates to the optimal integration of a new optimization technique, called Acceleration, which shortens the delay computation time, with known ones, such as Head cut-off, that stop delay computation at an early stage, under appropriate conditions. Seemingly, these two kinds of techniques work on orthogonal aspects of the computation, since Acceleration decreases the delay computation time for any given trajectory, whereas Head cut-off decreases the number of trajectories whose delay is eventually computed. So, one might expect that optimal integration of these techniques ought to result from their combination with parameter values that are respectively optimal for each technique considered in isolation. At a closer look, however, this expectation proves ill-founded, because of actual interference between the techniques in question.
A key idea to obtain near-optimal integration of Acceleration with Head cut-off is that of appropriately smoothing the former in order to prevent the loss of information that would harm the effectiveness of the latter. This, together with the computational power made available by the Cometa Grid Infrastructure has enabled one to nearly quadruplicate the size of the search space explored so far. The software is open source, written in standard C++, but for a few scripts, mostly meant for job monitoring and control on the Cometa Grid, and will be made freely available on the PI2S2 Web in the GRID CT Wiki. Besides its inherent research purpose, the application may serve as a testbed to experiment with job control methods in computational grids. Furthermore, use of the application is also meant to serve educational purposes.