Concurrent Algorithms as Space-Time Recursion Equations

Abstract

Recent developments in the technology of fabricating large-scale integrated circuits have made it possible to implement computing systems that use many hundred thousands of transistors to achieve a given task. An interesting design will have high computational complexity rather than merely vast numbers of identical simple components such as memory elements. Such a design can be represented as a fully instantiated implementation of objects of the implementation medium (e.g., transistors in VLSI technology) or as successive hierarchical levels of implementations where each level is constructed of objects which are abstract models of the implementation at the level below it. The former allows implementation details at the bottom level to penetrate throughout the whole design. Such representation may be suited for machine execution but is hard to deal with from the designer's point of view, and verifying both its functionality and physical layout is costly. As the complexity of the design grows, the limitation of this approach becomes more apparent. The second approach is aimed at managing the complexity of a design. One breaks the design into successive levels of subsystems until each is of a manageable complexity-the hierarchical design method [11].

Additional details