The design of a parallel algorithm for the subject search on the Cometa grid is presented. Known optimization techniques of the basic algorithm are supplemented with novel ones. These, and especially the higher performance enabled by the 64-bit architecture, outperform current implementations on 32-bit machines by a rough 2.7 speed-up factor. This work introduces the basic algorithm, its optimization techniques and their mathematical underpinnings. The most novel aspect of this contribution relates to the optimal integration of a new optimization technique for delay computation, called Acceleration, with known ones, such as Head cut-off, that stop delay computation at an early stage, under appropriate conditions. The performance gain delivered by each of these techniques depends on user-defined parameters, easily amenable to empirical optimization. Seemingly, the 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 is exposed in detail in this work, where a more general applicability of this idea is argued as well. 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 is going to be made freely available on the PI2S2 Web in the GRID CT Wiki.
Looking for Class Records in the 3x+1 Problem by Means of the COMETA Grid Infrastructure
SCOLLO, Giuseppe
2008-01-01
Abstract
The design of a parallel algorithm for the subject search on the Cometa grid is presented. Known optimization techniques of the basic algorithm are supplemented with novel ones. These, and especially the higher performance enabled by the 64-bit architecture, outperform current implementations on 32-bit machines by a rough 2.7 speed-up factor. This work introduces the basic algorithm, its optimization techniques and their mathematical underpinnings. The most novel aspect of this contribution relates to the optimal integration of a new optimization technique for delay computation, called Acceleration, with known ones, such as Head cut-off, that stop delay computation at an early stage, under appropriate conditions. The performance gain delivered by each of these techniques depends on user-defined parameters, easily amenable to empirical optimization. Seemingly, the 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 is exposed in detail in this work, where a more general applicability of this idea is argued as well. 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 is going to be made freely available on the PI2S2 Web in the GRID CT Wiki.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
