Synchronizing Large Systolic Arrays

Allan L. Fisher; H. T. Kung

doi:10.1117/12.933695

28 December 1982 Synchronizing Large Systolic Arrays

Allan L. Fisher, H. T. Kung

Proceedings Volume 0341, Real-Time Signal Processing V; (1982) https://doi.org/10.1117/12.933695
Event: 1982 Technical Symposium East, 1982, Arlington, United States

Abstract

Parallel computing structures consist of many processors operating simultaneously. If a concurrent structure is regular, as in the case of a systolic array. it may be convenient to think of all processors as operating in lock step. This synchronized view, for example, often makes the definition of the structure and its correctness relatively easy to follow. However, large, totally synchronized systems controlled by central clocks are difficult to implement because of the inevitable problem of clock skews and delays. An alternative means of enforcing necessary synchronization is the use of self-timed, asynchronous schemes, at the cost of increased design complexity and hardware cost. Realizing that different circumstances call for different synchronization methods, this paper provides a spectrum of synchronization models; based on the assumptions made for each model, theoretical lower bounds on clock skew are derived, and appropriate or best-possible synchronization schemes for systolic arrays are proposed. In general, this paper represents a first step towards a systematic study of synchronization problems for large systolic arrays. One set of models is based on assumptions that allow the use of a pipelined clocking scheme, where more than one clock event is propagated at a time. In this case, it is shown that even assuming that physical variations along clock lines can produce skews between wires of the same length, any one-dimensional systolic array can be correctly synchronized by a global pipelined clock while enjoying desirable properties such as modularity, expandability and robustness in the synchronization scheme. This result cannot be extended to two-dimensional arrays, however--the paper shows that under this assumption, it is impossible to run a clock such that the maximum clock skew between two communicating cells will be bounded by a constant as systems grow. For such cases or where pipelined clocking is unworkable, a synchronization scheme incorporating both clocked and "asynchronous" elements is proposed.

Citation Download Citation

Allan L. Fisher and H. T. Kung "Synchronizing Large Systolic Arrays", Proc. SPIE 0341, Real-Time Signal Processing V, (28 December 1982); https://doi.org/10.1117/12.933695

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available