臺灣博碩士論文加值系統

在微米製程上，晶片網路的概念已經被提出來解決晶片系統上的溝通問題。一個完整的晶片網路設計需考量到軟體和硬體兩方面的架構。硬體的架構包括了多種不同型態之處理元件的選擇和硬體架構的排列方式。軟體的設計上需要考量每個程序要在哪個處理元件上面執行和執行的順序以及程序間的溝通。對一個目標程式而言，為了找到最佳的硬體設計，需要同時考量軟體和硬體兩方面。先前相關的成果已經提出了一些共同合成演算法，他們的設計目標是針對嵌入式系統上面的應用程式，在符合時間需求的狀況下讓能源消耗越小越好。在這篇論文中，我們將以下幾種不同形態演算法所跑出來的解和跑出解的時間。所比較的演算法包含了發展分支定界演算法、疊代演算法和四種以模擬冶鐵為基礎的演算法。

Network-on-Chip (NoC) has been proposed to overcome the complex on-chip communication problem of SoC (System-on-Chip) design in deep submicron. A complete NoC design contains exploration on both hardware and software architectures. The hardware architecture includes the selection of PEs (Processing Elements) with multiple types and their topology. The software architecture contains the allocation of tasks to PEs, scheduling of tasks and their communications. To find the best hardware design for the target tasks, both hardware and software architectures need to be considered simultaneously. Previous works on NoC design have proposed some co-synthesis algorithms, which minimizes energy consumption while meeting the real-time requirements commonly seen in the embedded applications. In this thesis, we compare the solution quality and running time of several types of co-synthesis algorithms including branch and bound algorithm, iteraitve algorithm and SA-based algorithm.

Acknowledge i
Chinese Abstract ii
Abstract iii
1 Introduction 1
2 Related Work 5
3 System Specifications and Problem formulation 7
3.1 System Specifications . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 10
4 The Architectural Co-Synthesis Algorithm 12
4.1 The Branch and Bound Algorithm . . . . . . . . . . . . . . . 12
4.1.1 BranchMethod . . . . . . . . . . . . . . . . . . . . . . 13
4.1.2 Bounding Method . . . . . . . . . . . . . . . . . . . . . 15
4.2 The Iterative Algorithm . . . . . . . . . . . . . . . . . . . . . 17
4.3 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . 20
4.3.1 LTM-PS: Low TemperatureMove on PS . . . . . . . . 25
4.3.2 Greedy PE-SelectionMethod . . . . . . . . . . . . . . 25
4.3.3 The Two-Stage SA Algorithm . . . . . . . . . . . . . . 26
5 Experimental Results 28
5.1 Experimental Settings . . . . . . . . . . . . . . . . . . . . . . 28
5.2 Experimental Result - Solution Quality . . . . . . . . . . . . . 31
5.3 Execution Time Evaluation . . . . . . . . . . . . . . . . . . . 35
6 Conclusion 38
Bibliography 40

[1] ARM Processor cores. http://www.arm.com/products/CPUs/.
[2] Electronics. Philips’ IP portfolio. http://www.semiconductors.philips.com.
[3] SimpleScalar. http://www.simplescalar.com/.
[4] Texas Instruments. Digital Signal Processing
. http://focus.ti.com/dsp/docs/dsphome.tsp?sectionId=46.
[5] MPEG-2 video. is standard. I. D. 13818-2, 2001.
[6] L. Benini and G. D. Micheli. Network on chips: A new soc paradigm.
IEEE Computers, 35:70–78, January 2002.
[7] T. H. Coreman, C. E. Leiserson, R. L. Rivest, and C. Stain. Introduction
to Algoirthms. McGraw Hill.
[8] W. J. Dally and B. Towles. Route packets, not wires: On-chip interconnection
networks. Proc. Design Automation Conference (DAC), pages
684–689, June 2001.
[9] C. J. Glass and L. M. Ni. The turn model for adaptive routing. Proc.
international Symposium on Computer Architecture (ISCA), pages 278–
287, May 1992.
[10] M. Grajcar. Strengths and weakness of genetic list scheduling for heterogeneous
systems. Proc. International Conference on Application of
Concurrency to System Design (ACSD), pages 123–132, June 2001.
[11] A. Hemani, A. Jantsch, S. Kumar, A. Postula, J. ぴOberg, M. Millberg,
and D. Lindqvist. Network on a chip: An architecture for billion transistor
era. Proc. of the IEEE NorChip, 220(4598):671–680, November
2000.
[12] J. Hu and R. Marculescu. Energy-aware mapping for tile-based noc
architectures under performance constraints. IEEE ASP-DAC, January
2003.
[13] J. Hu and R. Marculescu. Energy-aware communication and task
scheduling for network-on-chip architecture under real-time constraints.
Proc. Design, Automation and Testing in Europe Conference and Exhibition
(DATE), 2004.
[14] W.-H. Hung, Y.-J. Chen, C.-L. Yang, Y.-S. Chang, and A. P. Su. An
architectural co-synthesis algorithm for energy-aware network-on-chip
design. Proc. SAC, March 2007.
[15] D. L. R. Robert P. Dick and W. Wolf. Tgff: Task graphs for free. Proc.
Intl. Workshop on Hardware/Software Codesign, pages 97–101, March
1998.
[16] J.-P. S. Shashi Kumar, Axel Jantsch, M. Forsell, M. Millberg, J. ぴOberg,
K. Tiensyrjぴa, and A. Hemani. A network on chip architecture and design
methodology. Proc. Symposium on VLSI, pages 117–124, April 2002.
[17] D. Shin and J. Kim. Power-aware communication optimization for
network-on-chips with voltage scalable links. Proc. CODES+ISSS,
September 2004.
[18] G. C. Sih and E. A. Lee. A compile-time scheduling heuristic
for interconnection-constrained heterogeneous processor architectures.
IEEE Transactions on Parallel and Distributed Systems, 4(2):175–187,
February 1993.
[19] L. B. Terry Tao Ye and G. D. Micheli. Analysis of power consumption
on switch fabrics in network routers. Proc. of Design Automation
Conference (DAC), pages 524–529, June 2002.
[20] K. C. Thomas L. Adam and J. Dickson. A comparison of list schedules
for parallel processing systems. Commun. ACM, 17(12):685–690,
December 1974.
[21] W. H. Wolf. Hardware-software codesign of embedded systems. Proc.
of the IEEE, 8(7):967–989, July 1994.
[22] W. H. Wolf. An architectural co-synthesis algorithm for distributed,
embedded computing systems. IEEE Transaction on Very Large Scale
Integration (VLSI) Systems, 5, June 1997.