MAGELLAN: multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs

ABSTRACT

The paper presents MAGELLAN, a heuristic technique for mapping hierarchical control-dataflow task graph specifications on heterogeneous architecture templates. The architecture can consist of multiple hardware and software processing elements as specified by the user. The objective of the technique is to minimize the worst case latency of the task graph subject to the area constraints on the architecture. The technique uses an iterative approach consisting of closely linked hardware-software partitioner and scheduler. Both the partitioner and scheduler operate on the task graph in a hierarchical top down manner. The technique optimizes deterministic loop constructs by applying clustering, unrolling and pipelining. The technique considers speculative execution for conditional constructs. The number of actual hardware/software implementations of a function in the task graph are also optimized by the technique. The effectiveness of the technique is demonstrated by a case study of an image compression algorithm.

REFERENCES

• 1: Hidehiro Takata , Tetsuya Watanabe , Tetsuo Nakajima , Takashi Takagaki , Hisakazu Sato , Atsushi Mohri , Akira Yamada , Toshiki Kanamoto , Yoshio Matsuda , Shuhei Iwade , Yasutaka Horiba, The D30V/MPEG Multimedia Processor, IEEE Micro, v.19 n.4, p.38-47, July 1999 [doi>10.1109/40.782566]
• 2: Mitsuo Ikeda , Toshio Kondo , Koyo Nitta , Kazuhito Suguri , Takeshi Yoshitome , Toshihiro Minami , Hiroe Iwasaki , Katsuyuki Ochiai , Jiro Naganuma , Makoto Endo , Yutaka Tashiro , Hiroshi Watanabe , Naoki Kobayashi , Tsuneo Okubo , Takeshi Ogura , Ryota Kasai, SuperENC: MPEG-2 Video Encoder Chip, IEEE Micro, v.19 n.4, p.56-65, July 1999 [doi>10.1109/40.782568]
• 3: Rajesh Kumar Gupta , Giovanni De Micheli, Co-Synthesis of Hardware and Software for Digital Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 1995
• 4: R. Ernst et al. "The COSYMA environment for hardwaro/softvmre cosynthesis of small embedded systems". Journal of Microprocessors ond Microsgstems, 20, 1996.
• 5: Asawaree Prabhakar Kalavade , Edward A. Lee, System-level codesign of mixed hardware-software systems, 1995
• 6: Smita Bakshi , Daniel D. Gajski, A scheduling and pipelining algorithm for hardware/software systems, Proceedings of the 10th international symposium on System synthesis, p.113-118, September 17-19, 1997, Antwerp, Belgium
• 7: Ralf Niemann , Peter Marwedel, Hardware/Software Partitioning using Integer Programming, Proceedings of the 1996 European conference on Design and Test, p.473, March 11-14, 1996
• 8: J: Jeon and K. Cboi. Loop Pipelining in Herdware-Software Partitioning". In Proceedings of ASPDAC, 1998.
• 9: Karam S. Chatha , Ranga Vemuri, RECOD: a retiming heuristic to optimize resource and memory utilization in HW/SW codesigns, Proceedings of the 6th international workshop on Hardware/software codesign, p.139-143, March 15-18, 1998, Seattle, Washington, United States
• 10: Ti-Yen Yen , Wayne Wolf, Hardware-Software Co-Synthesis of Distributed Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 1996
• 11: B.P. Dave and N.K. Jha. "COHRA: Herdware-Software Co-Synthesis of Hierarchical Heterogenous Distributed Embedded Systems". 17(10), October 1998.
• 12: B..P. Dick end N.K. Jh&. "MOGAC: A Multiobjective Genetic Algorithm for Hardwaro-Softwere Cosynthesis of Distributed Embedded Systems". 17(10), October 1998.
• 13: Bharat P. Dave , Ganesh Lakshminarayana , Niraj K. Jha, COSYN: hardware-software co-synthesis of heterogeneous distributed embedded systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.1, p.92-104, March 1999 [doi>10.1109/92.748204]
• 14: F. Ba}arln, L. Lavegno, P. Murthy, end A. Sangiovanni-Vincentelli. "Scheduling for Embedded tteal-Time Systems". January-Mereh 1998.
• 15: K.S. Chatha and R. Vemuri. "An Iterative Algorithm for Hardware-Software Partitioning, Hardware Design Space Exploration and Scheduling. "Design Automation for Embedded Systems , (5):281-293, 2000.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Management, Theory