Contents 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Parallel Computer System Modeling . . . . . . . . . . . . . . . 2 1.1.2 Object-Oriented Synthesis . . . . . . . . . . . . . . . . . . . 4 1.1.3 Intelligent Fuzzy Concurrent Design . . . . . . . . . . . . . . 5 1.1.4 System Simulation and Performance Evaluation . . . . . . . . . 7 1.1.5 Formal Synthesis Model . . . . . . . . . . . . . . . . . . . . 7 1.2 Contributions and Organization . . . . . . . . . . . . . . . . . . . 8 2 CONCEPTS AND TECHNIQUES . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1 Object-Oriented Modeling . . . . . . . . . . . . . . . . . . . . . . 10 2.1.1 Object-Oriented Structure . . . . . . . . . . . . . . . . . . . 11 2.1.2 Object-Oriented Relationships . . . . . . . . . . . . . . . . . 13 2.2 Object-Oriented Synthesis . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Fuzzy Design-Space Exploration . . . . . . . . . . . . . . . . . . . 18 2.5 Concurrent Synthesis . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6 Object-Oriented Simulation . . . . . . . . . . . . . . . . . . . . . 20 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 PERFORMANCE SYNTHESIS METHODOLOGY*. . . . . . . . . . . . . . . . . . . . 23 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Problem Specification and Input Descriptions . . . . . . . . . . . . 25 3.2.1 Problem Specification . . . . . . . . . . . . . . . . . . . . . 25 3.2.2 System Input . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Performance Synthesis Methodology . . . . . . . . . . . . . . . . . . 36 3.3.1 Map to Architecture Models Phase . . . . . . . . . . . . . . . 37 3.3.2 Generate System Configurations Phase . . . . . . . . . . . . . 39 3.3.3 Synthesize Architecture Phase . . . . . . . . . . . . . . . . . 40 3.3.4 Top-Down Topology . . . . . . . . . . . . . . . . . . . . . . . 52 3.4 Application Examples . . . . . . . . . . . . . . . . . . . . . . . . 53 3.4.1 Cluster Array Processor . . . . . . . . . . . . . . . . . . . . 54 3.4.2 Sorting Example . . . . . . . . . . . . . . . . . . . . . . . . 59 3.4.3 Other Examples . . . . . . . . . . . . . . . . . . . . . . . . 61 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4 OBJECT-ORIENTED CONCURRENT SYNTHESIS METHODOLOGY**. . . . . . . . . . . . 66 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2 Previous Work and Motivation . . . . . . . . . . . . . . . . . . . . 67 4.3 Object-Oriented Concurrent Synthesis Methodology. . . . . . . . . . . 69 4.3.1 Specification Language . . . . . . . . . . . . . . . . . . . . 69 4.3.2 Specification Analysis Phase . . . . . . . . . . . . . . . . . 73 4.3.3 Concurrent Design Phase . . . . . . . . . . . . . . . . . . . . 74 4.3.4 System Integration Phase . . . . . . . . . . . . . . . . . . . 84 4.4 Application Examples . . . . . . . . . . . . . . . . . . . . . . . . 89 4.4.1 Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.4.2 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.4.3 Example 3 . . . . . . . . . . . . . . . . . . . . . . . . . . .101 4.4.4 Observations . . . . . . . . . . . . . . . . . . . . . . . . . .104 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .105 5 MULTI-TOKEN OBJECT-ORIENTED BI-DIRECTIONAL NET*** . . . . . . . . . . . .107 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .108 5.2 Concurrent Synthesis and Motivation Goals . . . . . . . . . . . . . .109 5.2.1 Concurrent Object-Oriented System-Level Synthesis . . . . . . .109 5.2.2 Motivating Goals . . . . . . . . . . . . . . . . . . . . . . .111 5.3 Multi-token Object-Oriented Bi-directional Net Model. . . . . . . . .112 5.4 Model Validation. . . . . . . . . . . . . . . . . . . . . . . . . . .119 5.5 Modeling Design Completion Check. . . . . . . . . . . . . . . . . . .126 5.6 Modeling Synthesis Rollback . . . . . . . . . . . . . . . . . . . . .131 5.7 Application Examples. . . . . . . . . . . . . . . . . . . . . . . . .135 5.7.1 Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . . .135 5.7.2 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . .139 5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142 6 MULTI-LEVEL INTELLIGENT SYNTHESIS AND SIMULATION ENVIRONMENT. . . . . . .143 6.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . .143 6.2 Related Research Results . . . . . . . . . . . . . . . . . . . . . .144 6.2.1 Fault-Tolerant Multistage Interconnection Networks . . . . . .145 6.2.2 Multiprocessor Task Scheduling . . . . . . . . . . . . . . . .146 6.2.3 Hypercube Programs. . . . . . . . . . . . . . . . . . . . . . .147 6.3 Multi-level Intelligent Synthesis and Simulation Environment. . . . .148 6.3.1 Multiprocessor Modeling . . . . . . . . . . . . . . . . . . . .150 6.3.2 Multiprocessor Synthesis . . . . . . . . . . . . . . . . . . .153 6.3.3 Multiprocessor Simulation . . . . . . . . . . . . . . . . . . .156 6.3.4 MISSE Design Levels . . . . . . . . . . . . . . . . . . . . . .164 6.4 Comparison between PSM and OOCSM . . . . . . . . . . . . . . . . . .168 6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .169 7 CONCLUSION AND FUTURE WORK. . . . . . . . . . . . . . . . . . . . . . . .171 Note: * Chapter 3 has been published as: Pao-Ann Hsiung, Sao-Jie Chen, Tsung-Chien Hu, and Shih-Chiang Wang, "PSM: An Object-Oriented Synthesis Approach to Multiprocessor System Design," IEEE Trans. on VLSI Systems, Vol. 4, No. 1, pp. 83-97, March 1996. ** Chapter 4 is to be published as: Pao-Ann Hsiung, Chung-Hwang Chen, Trong-Yen Lee, and Sao-Jie Chen, "ICOS: An Intelligent Concurrent Object-Oriented Synthesis Methodology for Multiprocessor Systems," To appear in ACM Trans. on Design Automation of Electronic Systems. *** Chapter 5 has been published as: Pao-Ann Hsiung, Trong-Yen Lee, and Sao-Jie Chen, "MOBnet: An Extended Petri Net Model for the Concurrent Object-Oriented System-level Synthesis of Multiprocessor Systems," IEICE Trans. on Information and Systems, Vol. E80-D, No. 2, pp. 232-242, February 1997.