| Synchronization is often necessary in parallel computing, but it can create delays whenever the receiving processor is idle, waiting for the information to arrive. This is especially true for barrier, or global, synchronization, in which every processor must synchronize with every other processor. Nonetheless, barriers are the only form of synchronization explicitly supplied in OpenMP, and they occur whenever collective communication operations are used in MPI.;Many applications do not actually require global synchronization; local synchronization, in which a processor synchronizes only with those processors from which it has an incoming edge in some directed graph, is often adequate. However, the behavior of a system under local synchronization is more difficult to analyze, since processors do not start tasks at the same time.;This thesis shows an exact limit, constant with the number of processors, for synchronization time in the case where the synchronization graph is a directed cycle and the task times are geometrically distributed with p = 0.5. Under global synchronization, however, the time is unbounded, increasing logarithmically with the number of processors. Similar results also apply for p ≠ 0.5.;Combinatorial properties of the Markov chain induced by undirected-cycle synchronization are shown, with possible future applications to constructing bounds on the synchronization time.;A new proof is given for the constant upper bounds that apply when tasks are normally distributed and the synchronization graph is any graph of bounded degree.;It is also shown that for some power-law distributions on the tasks, there is no constant upper bound as the number of processors increases, even for the directed cycle.;The thesis also examines the cost of synchronization in systems with hatching, whereby each processor completes several tasks before synchronizing, as yet another way to improve efficiency. Analytic and simulation results showing the results of hatching with both barrier and send/receive synchronization models, where the task times can assume a variety of probability distributions, are provided. For the geometric and exponential distributions and cyclic dependencies; by using local synchronization and hatching one can achieve any desired efficiency with a hatching size independent of the number of processors. In contrast, for global synchronization and a fixed batch size, whenever the distribution has infinite support the efficiency will go to 0 as the number of processors tends to infinity.;Simulation results are provided for a variety of distributions and synchronization models. |
