EFFICIENT TECHNIQUES FOR PERFORMING AN IRREGULAR COMPUTATION ON DISTRIBUTED-MEMORY MACHINES

Two techniques to perform an irregularly structured Grobner basis comp utation (a basic method used in symbolic polynomial manipulation) on d istributed memory machines are developed. The first technique, based o n relaxation of dependencies present in the sequential computation, ex ploits coarse-grain parallelism. In this so-called relaxation approach , at every step, each processor reduces a local pair if available, com municates the result and status information from other processors, and updates the local set of pairs and basis. The basis is replicated on each processor while the set of pairs is distributed across the proces sors. The computation terminates when no pairs are left to be reduced on each processor. A relaxation algorithm based on this approach, alon g with its experimental results, are provided. The other technique, na med quasi-barrier, is developed to enhance the performance of the rela xation algorithm. Using this technique, load balance and performance c an be improved by synchronizing p processors when a fraction of the ac tive task are completed. The performance enhancement is significant fo r large numbers of processors when the distribution of pair reduction times is close to exponential. The experimental results obtained on In tel Paragon and IBM SP2 demonstrate the effectiveness of these techniq ues.