Joint application mapping/interconnect synthesis techniques for embedded chip-scale multiprocessors

• Published in: IEEE transactions on parallel and distributed systems 2005-02, Vol.16 (2), p.99-112
• Main Authors: Bambha, N.K., Bhattacharyya, S.S.
• Format: Article
• Language: English
• Subjects: Algorithms; Application software; Computer architecture; Embedded multiprocessors; Interconnect; interconnect synthesis; Power system interconnection; Processor scheduling; scheduling; Scheduling algorithm; Signal processing algorithms; Signal synthesis; Studies; System recovery; task graphs; Topology; Transistors
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2005.20

As transistor sizes shrink, interconnects represent an increasing bottleneck for chip designers. Several groups are developing new interconnection methods and system architectures to cope with this trend. New architectures require new methods for high-level application mapping and hardware/software codesign. We present high-level scheduling and interconnect topology synthesis techniques for embedded multiprocessor systems-on-chip that are streamlined for one or more digital signal processing applications. That is, we seek to synthesize an application-specific interconnect topology. We show that flexible interconnect topologies utilizing low-hop communication between processors offer advantages for reduced power and latency. We show that existing multiprocessor scheduling algorithms can deadlock if the topology graph is not strongly connected, or if a constraint is imposed on the maximum number of hops allowed for communication. We detail an efficient algorithm that can be used in conjunction with existing scheduling algorithms for avoiding this deadlock. We show that it is advantageous to perform application scheduling and interconnect synthesis jointly, and present a probabilistic scheduling/interconnect algorithm that utilizes graph isomorphism to pare the design space.