含傳輸延遲之多處理機排程方法的設計與評估

Abstract

在含有傳輸延遲之多處理機系統的排程方法中，ETF 是目前具有最好的最壞情況績效 （worst-case bound）。在這篇論文中，我們將提出一個ETF 改良方法，稱為ETF ╱ CP。經由模擬實驗，我們證明ETF ╱CP在排程長度（schedule length） 的平均績效 （average-case performance）表現上，遠較ETF 好。 除了排程長度外，我們尚討論了另外二種評估基準，即效率漏失（efficiency loss ）及遮掩程度（hidden overhead） 。效率漏失可測量一個排程與最佳排程相差多少 的程度。而遮掩程度強調：一個好的排程有較少的傳輸負擔。由此，欲知多少傳輸延 遲被遮掩便可藉由遮掩程度來評估。 對更廣泛的排程問題－在異處理機系統下之排程，我們亦提出了一個EFTF演算法。模 擬實驗顯示：在異處理機系統下，EFTF比ETF 有較好的平均績效。