LOW-COST, HIGH-PERFORMANCE BARRIER SYNCHRONIZATION ON NETWORKS OF WORKSTATIONS

Circulating active barrier (CAB) is a new low-cost, high-performance h ardware mechanism for synchronizing multiple processing elements (PEs) in networks of workstations at fine-grained programmed barriers. CAB is significantly less complex than other hardware barrier synchronizat ion mechanisms with equivalent performance, using only a single conduc tor, such as a wire or copper run on a printed-circuit board, to circu late barrier packets between PEs. When a PE checks in at a barrier, th e CAB hardware will decrement the count associated with that barrier i n a bit-serial fashion as a barrier packet passes through, and then wi ll monitor the packets until all PEs have checked in at the barrier. T he ring has no clocked sequential logic in the serial loop. A cluster controller (CC) generates packets for active barriers, removes packets when no longer needed, and resets counters when all PEs have seen the zero-count. A hierarchy of PEs can be achieved by connecting the CCs in intercluster rings. When using conservative timing assumptions, the expected synchronization times with optimal clustering are shown to b e under 1 mu s for as many as 4096 PEs in multiprocessor workstations or 1024 single-processor workstations. The ideal number of clusters fo r a two-dimensional hierarchy of N PEs is shown to be [N(D + G)/(I + G )](1/2), where G is the gate propagation delay, D is the inter-PE dela y, and I is the intercluster transmission time. CAB allows rapid, cont ention-free check-in and proceed-from-barrier and is applicable to a w ide variety of system architectures and topologies. (C) 1997 Academic Press.