National Changhua University of Education Institutional Repository : Item 987654321/14022

English | 正體中文 | 简体中文 | Items with full text/Total items : 6507/11669
Visitors : 30338459 Online Users : 443

RC Version 3.2 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

Scope Adv. Search

Login ‧ Upload ‧ Help ‧ About ‧ Administer

NCUEIR > College of Engineering > eedept > Books > Item 987654321/14022

Please use this identifier to cite or link to this item: http://ir.ncue.edu.tw/ir/handle/987654321/14022

Title:	一組用於限時排序問題之演算法 A Class of Time-Constrained Scheduling Algorithms
Authors:	吳宗益
Contributors:	電子工程學系
Keywords:	限時排序;資料路徑合成;高階合成;排序;配置;運算;控制步驟;運算元件 (TIME-CONSTRAINED);(DATA PATH SYNTHESES);(HIGH LEVEL SYNTHEIS);(SCHEDVLING);(ALLOCATION);(OPERATION);(CONTROL-STEP);(FUNCTION UNIT)
Date:	1991
Issue Date:	2012-09-10T02:54:09Z
Publisher:	國立清華大學
Abstract:	資料路徑合成(Data Path Synthesis) 是高階合成(High Level Synthesis)中的一個最重要的工作。一般資料路徑合成可分成二個子工作：一為排序(Scheduling), 另一個為配置(Allocation)。排序決定每一個運算(Operation) 要在那一個控制步驟(Control-step)執行，而配置決定每一個運算要由那一個運算元件(Function unit) 來執行。排序問題更可細分為時限(Time-constrained)排序與資源限制(Time-constrained)排序。至於資料路徑合成的目的則在提高資料路徑的執行速度與降低其硬體成本。在本篇論文中，我們提出一組於時限排序問題的演算法。力導向排序(Force-directed Scheduling) 法只是我的方法的一個成員。我的排序方法首先用儘早排序(ASAP Scheduling) 與儘遲排序(ALAP Scheduling) 產生初始的部分排序，然後逐次的利用我所定義的動作(Action)去減少某個運算在排序上的可移度(Mobility), 一直到所有運岸被排好為止。由於每次要減少可移度的運算可能不只一個，所以須要靠成本函數(Cost Function) 來決定如何挑其中的一個，我所提供的成本函數考慮每個運算的危疾度(Critical)，和估計每一個排序要花費的硬體成本與分布圖(Distribution Graph)的均勻程度。除了上述的方法，我還提出如何利用分化與征服(Divide-and-conquer)減少排序所用的時間,并利用一新的精煉演算法來提高分化與征服法所產生結果的品質。所有我所提出來的方法都在SUN 公司的SPARC 電腦上完成程度的寫作與測試無誤。我用了五個例子來測試我的程式的品質。這五個例子由我的程式排序後都有不錯的結果，甚致勝過力導向排序法。而且分化與征服法只要花非常短的時間就可排出不錯的結果。
Relation:	碩士, 國立清華大學資訊科學學系
Appears in Collections:	[eedept] Books

Files in This Item:

File	Size	Format
2050300611001.pdf	59Kb	Adobe PDF	1054	View/Open

Loading...