A methodology and algorithms for the design of hard real-time multitasking ASICs

ABSTRACT

Traditional high-level synthesis concentrates on the implementation of a single task (e.g. filter, linear controller, A/D converter). However, many applications—multifunctional embedded controllers intelligent wireless end-points, and DSP and multimedia servers—are defined as sets of several computational tasks. This paper describes new techniques for the synthesis of ASIC implementations that realize multiple computational processes under hard real-time constraints. Our synthesis methodology establishes connections between two important comengineering domains: operating systems and behavioral synthesis. Our hierarchical approach starts from an incompletely-specified preliminary solution and uses, interchangeably, operating system and behavioral synthesis techniques to derive increasingly more detailed and accurate design solutions. We have experimented with both optimal and heuristic algorithms to implement this methodology. The optimal algorithm uses several heuristics to speed up the average run time of an exhaustive branch-and-bound search. Force-directed optimization is the core of the heuristic synthesis method. Analysis of the proposed algorithms and the experiments shows that matching the number of bits and type of operational in taskes assigned to the same application-specific processor was the most important factor in obtaining area-efficient designs.

REFERENCES

• 1: George S. Almasi , Allan Gottlieb, Highly parallel computing (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 2: P. Altenbernd, Deadline-monotonic software scheduling for the co-synthesis of parallel hard real-time systems, Proceedings of the 1995 European conference on Design and Test, p.190, March 06-09, 1995
• 3: BANNISTER, g. A. AND TRIVEDI, K. S. 1983. Task allocation in fault-tolerant distributed systems. Acta Inf. 20, 3, 261-283.
• 4: BOREL, J. 1997. Technologies for multimedia systems on a chip. In Proceedings of the IEEE International Conference on Solid-State Circuits. IEEE Computer Society Press, Los Alamitos, CA, 18-21.
• 5: Mauricio Breternitz, Jr. , John Paul Shen, Architecture synthesis of high-performance application-specific processors, Proceedings of the 27th ACM/IEEE conference on Design automation, p.542-548, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123398]
• 6: BRODERSEN, R.W. 1997. The network computer and its future. In Proceedings of the IEEE International Conference on Solid-State Circuits. IEEE Computer Society Press, Los Alamitos, CA, 32-36.
• 7: CAMPOSANO, R. AND BRAYTON, R. 1987. Partitioning before logic synthesis. In Proceedings of the International Conference on Computer-Aided Design (ICCAD). 324-326.
• 8: Samit Chaudhuri , Robert A. Walker, Computing lower bounds on functional units before scheduling, Proceedings of the 7th international symposium on High-level synthesis, p.36-41, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 9: CHANDRAKASAN, A. P., POTKONJAK, M., MEHRA, R., RABAEY, J., AND BRODERSEN, R. 1995. Optimizing power using transformations. IEEE Trans. CAD 14 (Jan.), 13-32.
• 10: Pai Chou , Elizabeth A. Walkup , Gaetano Borriello, Scheduling for Reactive Real-Time Systems, IEEE Micro, v.14 n.4, p.37-47, August 1994 [doi>10.1109/40.296156]
• 11: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 12: GAJSKI, D. D. AND KUN, R. H. 1993. Guest editor's introduction: New VLSI tools. IEEE Computer 16, 12, 11-14.
• 13: GAJSKI, D. D., VAHID, F., AND NARAYAN, S. 1994. A system-resign methodology: Executable specification refinement. In Proceedings of the Conference on EURO-DAC'94. 458-463.
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Catherine H. Gebotys, Optimal synthesis of multichip architectures, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.238-241, November 1992, Santa Clara, California, United States
• 16: GIBBS, W. W. 1994. Software's chronic crisis. Sci. Am. (Sept. 1994), 86-95.
• 17: Gert Goossens , Dirk Lanneer , Marc Pauwels , Francis Depuydt , Koen Schoofs , Augusli Kifli , Marco Cornero , Paolo Petroni , Francky Catthoor , Hugo De Man, Integration of medium-throughput signal processing algorithms on flexible instruction-set architectures, Journal of VLSI Signal Processing Systems, v.9 n.1-2, p.49-65, Jan. 1995 [doi>10.1007/BF02406470]
• 18: GRAHAM, R. L., LAWLER, E. L., LENSTRA, J. K., AND RINNOY KAN, A. H. G. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5, 287-326.
• 19: Lisa Guerra , Miodrag Potkonjak , Jan Rabaey, High level synthesis for reconfigurable datapath structures, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.26-29, November 07-11, 1993, Santa Clara, California, United States
• 20: GUPTA, R. AND DEMICHELI, G. 1990. Partitioning of functional models of synchronous digital systems. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'90). IEEE Computer Society Press, Los Alamitos, CA, 216-219.
• 21: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 22: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 23: Xiaobo Hu , Joseph G. D'Ambrosio , Brian T. Murray , Dah-Lain Tang, Codesign of Architectures for Automotive Powertrain Modules, IEEE Micro, v.14 n.4, p.17-25, August 1994 [doi>10.1109/40.296154]
• 24: HUANG, C-H., YEN, J-Y., AND OUHYOUNG, M. 1996. The design of a low cost motion chair for video games and MPEG video playback. IEEE Trans. Consumer Electron. 42, 4, 991-997.
• 25: IEEE. 1991. Real-Time extensions to POSIX. 1003.4. IEEE Standards Office, New York, NY.
• 26: IEEE. 1993. Futurebus+ Recommended Practice. IEEE Standards Office, New York, NY.
• 27: ISMAIL, T. B., O'BRIEN, K., AND JERRAYA, A. 1994. Interactive system-level partitioning with PARTIF. In Proceedings of the European Conference on Design Automation (EURO-DAC '94, Grenoble, France, Sept. 19-23, 1994), J. Mermet, Ed. IEEE Computer Society Press, Los Alamitos, CA.
• 28: JACKSON, J. R. 1969. Scheduling a Production Line to Minimize Maximum Tardiness. Res. Rep. 43. Management Science Project. University of California at Los Angeles, Los Angeles, CA.
• 29: Kyosun Kim , Ramesh Karri , Miodrag Potkonjak, Synthesis of application specific programmable processors, Proceedings of the 34th annual conference on Design automation, p.353-358, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266164]
• 30: David Ku , Gionvanni De Micheli, Relative scheduling under timing constraints, Proceedings of the 27th ACM/IEEE conference on Design automation, p.59-64, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123227]
• 31: Kayhan Kükçakar , Alice C. Parker, CHOP: A constraint-driven system-level partitioner, Proceedings of the 28th conference on ACM/IEEE design automation, p.514-519, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127724]
• 32: KURDAHI, F. AND RAMACHANDRAN, C. 1993. Evaluating layout area tradeoffs for high level applications. IEEE Trans. Very Large Scale Integr. Syst. 1, 1, 46-55.
• 33: E. D. Lagnese , D. E. Thomas, Architectural partitioning for system level design, Proceedings of the 26th ACM/IEEE conference on Design automation, p.62-67, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74394]
• 34: LAWLER, E. L. AND MARTEL, C. U. 1982. Scheduling periodically occurring tasks on multiple processors. Inf. Process. Lett. 12, 1, 9-12.
• 35: Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987
• 36: LEHOCZKY, J. P., SHA, L., AND DING, Y. 1986. The rate monotonic scheduling algorithms - Exact characterization and average case behavior. In Proceedings of the IEEE Symposium on Real-Time Systems. IEEE Press, Piscataway, NJ, 181-191.
• 37: LEUNG, J. AND WHITEHEAD, J. 1982. On the complexity of fixed priority scheduling of periodic, real-time tasks. Perform. Eval. 2, 4, 237-250.
• 38: Rainer Leupers , Wolfgang Schenk , Peter Marwedel, Retargetable assembly code generation by bootstrapping, Proceedings of the 7th international symposium on High-level synthesis, p.88-93, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 39: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 40: Michael C. McFarland S.J., Computer-aided partitioning of behavioral hardware descriptions, Proceedings of the 20th conference on Design automation, p.472-478, June 27-29, 1983, Miami Beach, Florida, United States
• 41: MCFARLAND, M. C. AND PARKER, A. C. 1990. The high-level synthesis of digital systems. IEEE Computer 78, 2 (Feb. 1990), 301-317.
• 42: MCFARLAND, M. AND KOWALSKI, T. 1990. Incorporating bottom-up design into hardware synthesis. IEEE Trans. CAD 9, 9 (Sept. 1990).
• 43: MINOLI, D. AND KEINATH, R. 1994. Distributed Multimedia Through Broadband Communications Services. Artech House, Inc., Norwood, MA.
• 44: NAGARAJAN, R. AND VOGT, C. 1992. Guaranteed performance of multimedia traffic over the token ring. IBM Corp., Riverton, NJ.
• 45: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 46: PAULIN, P. G. AND KNIGHT, J. P. 1989. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE Trans. CAD 8, 6 (June 1989), 661-679.
• 47: Pierre G. Paulin , Clifford Liem , Trevor C. May , Shailesh Sutarwala, CodeSyn: a retargetable code synthesis system (abstract), Proceedings of the 7th international symposium on High-level synthesis, p.94, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 48: POTKONJAK, M. AND RABAEY, J. 1992. Scheduling algorithms for hierarchical data control flow graphs. Int. J. Circuits Theor. Appl. 20, 3, 217-234.
• 49: Miodrag Potkonjak , Jan Rabaey, Algorithm selection: a quantitative computation-intensive optimization approach, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.90-95, November 06-10, 1994, San Jose, California, United States
• 50: Miodrag Potkonjak , Wayne Wolf, Cost optimization in ASIC implementation of periodic hard-real time systems using behavioral synthesis techniques, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.446-451, November 05-09, 1995, San Jose, California, United States
• 51: Shiv Prakash , Alice C. Parker, Synthesis of application-specific multiprocessor architectures, Proceedings of the 28th conference on ACM/IEEE design automation, p.8-13, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127612]
• 52: J. M. Rabaey , C. Chu , P. Hoang , M. Potkonjak, Fast Prototyping of Datapath-Intensive Architectures, IEEE Design & Test, v.8 n.2, p.40-51, April 1991 [doi>10.1109/54.82037]
• 53: RABAEY, g. AND POTKONJAK, M. 1991. Complexity estimations for real time application specific circuits. In Proceedings of the 17th European Conference on Solid-State Circuits (Milan, Italy, Sept.). 201-204.
• 54: RABAEY, J. M. AND POTKONJAK, M. 1994. Estimating implementation bounds for real time DSP application specific circuits. IEEE Trans. CAD 13, 6 (June), 669-683.
• 55: Jayanth V. Rajan , Donald E. Thomas, Synthesis by delayed binding of decisions, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.367-373, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317914]
• 56: RAMAMRITHAM, K. AND STANKOVIC, J. 1994. Scheduling algorithms and operating system support for real-time systems. Proc. IEEE 82, 1 (Jan.), 55-67.
• 57: RATNER, R. S., SHAPIRO, E. B., ZEIDLER, H. M., WAHLSTROM, S. E., CLARK, C. B., AND GOLDBERG, J. 1973. Design of a fault tolerant airborne digital computer.
• 58: Daniel B. Schwartz, ATM scheduling with queuing delay predictions, ACM SIGCOMM Computer Communication Review, v.23 n.4, p.205-211, Oct. 1993
• 59: Lui Sha , John B. Goodenough, Real-Time Scheduling Theory and Ada, Computer, v.23 n.4, p.53-62, April 1990 [doi>10.1109/2.55469]
• 60: SHA, L., RAJKUMAR, R., AND LEHOCZKY, J. 1990. Real time scheduling support in Futurebus. In Proceedings of the 11th IEEE Symposium on Real-Time. IEEE Computer Society Press, Los Alamitos, CA, 331-340.
• 61: SHA, L., RAJKUMAR, R., AND SATHAYE, S. 1994. Generalized rate-monotonic scheduling theory: A framework for developing real-time systems. Proc. IEEE 82, 1 (Jan.), 68-82.
• 62: SHARMA, A. AND JAIN, R. 1993. Estimating architectural resources and performance for high-level synthesis applications. IEEE Trans. Very Large Scale Integr. Syst. 1, 2 (June), 175-190.
• 63: SOUKUP, J. 1981. Circuits layout. Proc. IEEE 69, 10 (Oct.), 1281-1304.
• 64: John A. StankovicThis work was done while the , Marco Spuri , Marco Di Natale , Giorgio C. Buttazzo, Implications of Classical Scheduling Results for Real-Time Systems, Computer, v.28 n.6, p.16-25, June 1995 [doi>10.1109/2.386982]
• 65: Ralf Steinmetz, Analyzing the Multimedia Operating System, IEEE MultiMedia, v.2 n.1, p.68-84, March 1995 [doi>10.1109/93.368605]
• 66: P. a. Subrahmanyam, Technical Activities Forum, Computer, v.30 n.2, p.92-93, February 1997
• 67: VAN CLEEMPUT, W. M. 1979. Hierarchical design for VLSI: problems and advantages. In Proceedings of the Caltech Conference on VLSI. 259-274.
• 68: WALKER, R. AND CAMPOSANO, R. 1991. A Survey of High-Level Synthesis Systems. Kluwer Academic Publishers, Hingham, MA.
• 69: WOLF, W. 1994. Hardware-software co-design of embedded systems. Proc. IEEE 82, 7 (July 1994), 967-989.
• 70: Xun Xiong , Edna Barros , Wolfgang Rosenstiel, A method for partitioning UNITY language in hardware and software, Proceedings of the conference on European design automation, p.220-225, September 19-23, 1994, Grenoble, France
• 71: YASUDA, H. 1997. Multimedia impact on devices in the 21st century. In Proceedings of the IEEE International Conference on Solid-State Circuits. IEEE Computer Society Press, Los Alamitos, CA, 28-31.
• 72: Ti-Yen Yen , Wayne Wolf, Communication synthesis for distributed embedded systems, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.288-294, November 05-09, 1995, San Jose, California, United States
• 73: Ti-Yen Yen , Wayne Wolf, An efficient graph algorithm for FSM scheduling, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.1, p.98-112, March 1996 [doi>10.1109/92.486084]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

General Terms:
Algorithms, Design, Performance