二元搜尋多核心平行運算處理器設計

Design of a Binary Search Based Multi-Core Parallel Computing Processor

尹華愚(Hua-Yu Yin)

指導教授 ： 蔡孟伸

國立臺北科技大學/機電學院/自動化科技研究所/碩士(2012年)

摘要

馮紐曼(Von Neumann)架構為今日普遍使用電腦架構之一，它運行方式之一是經由指令計數器得到下一指令位址。這些指令前後排列起來像條線，指令之間並無任何連結，因此電腦執行指令時如同沿著一條線上前後執行。在這種框架下要達到平行運算有其困難度。由於是單線執行，或是在不同處理器上執行單線作業，因為無法預知指令的相依性，如需進行平行運算或是資料交換，要提升到作業系統層級。本論文試圖設計可以平行運算之多核心處理器，該處理器指令格式是基於二元搜尋樹之理論。由於一個二元樹有兩連結可以指到互相獨立子樹。這些子樹由指令組成，而這些由指令形成互相獨立子樹可以平行執行。由於算數運算式可以使用二元樹表示，故可以利用這兩個連結，一個連結指向下一指令，另一連結指向另一獨立子樹頂端，因此這兩獨立子樹可平行計算，並且結果可以於這兩條子樹之父節點進行資料交換。這兩條由指令形成獨立子樹有如現今兩執行緒(thread)概念。本論文設計之電腦平行運算在硬體階層完成而非作業系統階層，因此設計的單晶片處理器可以不需作業系統而達成平行運算的目的。
由於指令格式非傳統形式，本論文以微軟VB6設計開發C語言程式編譯器。並透過兩個C語言程式進行測試。兩程式經編譯後機械碼送入以VHDL語言開發之多核形處理器之內以時序波形圖「Simulation Report」驗證多核心之平行運算。

關鍵字

二元搜尋 ； 多核心 ； 平行運算 ； 處理器

並列摘要

The von Neumann architecture is one of the basic architectures of modern computers, which gets the next instruction address based on the address counter. The Instructions list stored in the memory like a line. There is no link between instructions. When the computer is executing instructions step by step, it looks like walking along a line. It is a difficult task to achieve parallel computing with this architecture. This thesis attempts to design a processor which has multi-cores and is able to perform parallel computing. The instruction format is based on the theory of binary search tree. A binary tree presents with two links refered to two independent sub-trees. Since arithmetic statement can be presented as a binary tree, two links, one point to the next instruction address and the other point to the top of the other independence sub-tree are designed. Those independence sub-trees are able to perform in parallel. The instructions list of two independence sub-trees is similar to the concept of two threads. This thesis designs a computing architecture at the level of hardware rather than the level of operation system. A chip with this structure processor can perform parallel computing without operation system.
A C-language compiler with Microsoft VB6 is developed in order to generate machine codes. Two C programs are compiled by the compiler in order to verify the performance of proposed architecture. A multi-core processor is implemented in VHDL to verify the parallel processing performance of these machine codes.

並列關鍵字

Binary search ； Multi-core ； Parallel computing ； Processor

參考文獻

[2] M. J. Flynn and K. W. Rudd, " Parallel architectures", ACM Computing Surveys, vol. 28, no. 1, 1996, pp. 67-70.

[3] J. B. Dennis, "The Varietes of Data Flow Computers ",The Proceedings of the First International Conference on Distributed Computing Systems, Huntsville, AL. 1979. pp 1-16

[4] J. B. Dennis, " Data Flow Supercomputers ", IEEE, November 1980. pp 48-56.

[5] A. L. Davis and R. M. Keller, " Data Flow Program Graphs ", IEEE, 1982. pp 26-41.

[8] 吳嘉驊，平行編譯器中資料依賴性分析的改良，博士論文，國立成功大學資訊工程研究所，台南，2007。