TURING LECTURE THE SEARCH FOR PERFORMANCE IN SCIENTIFIC PROCESSORS JOHN COCKE
我感到榮幸和感激，能夠入選加入 ACM 圖靈獎得主之列。我可能花費了太多時間思考電腦，但我一點也不後悔。我很幸運地在計算領域初生之時進入，並參與了它的爆炸性成長。在過去30年中，底層技術的快速演進不僅提供了一個令人興奮的環境，也為我們這些試圖駕馭這種力量並將其發揮到極致的人帶來了持續不斷的智力挑戰。我必須趕快說，特別是對現場的年輕朋友們，前景無限。事實上，我相信未來三十年將更加令人興奮並充滿挑戰。
科學處理器性能的主要貢獻因素
科學處理器性能的三個主要貢獻因素是演算法、編譯器和機器組織。如果可能，同時優化這三個因素是獲得最高可能性能的關鍵。在這三個貢獻因素中，演算法改進最為重要。一個將演算法從 N**2 運算變為 N*logN 運算的點子，其中 N 與輸入元素的數量成比例，比機器組織的改進顯著得多，後者只能達到運行時間的常數因子改進。不幸的是，在底層機器組織中真正利用特定演算法的特性通常會產生一個專用電腦，它在大多數其他演算法上表現不佳。訊號處理器就是一個例子。它們處理資訊轉換非常快，甚至在一個時鐘週期內完成，但在計算其他任何東西時效率極低。
我的興趣一直在為廣泛的科學計算實現高性能。因此，我主要專注於涉及編譯器和底層機器架構的優化。未來，最高可能的性能改進很可能也必須包含更困難的演算法修改問題，這是因為平行性將至關重要，而平行機器的性能嚴重依賴於使用的演算法以及它與平行架構的匹配程度。
歷史趨勢與挑戰
在過去的25年中，我們看到單處理器電腦性能提高了100倍。我們也看到成本下降了10,000倍。在未來25年，我們很可能看到類似的成本改進。然而，由於次奈秒週期將很困難，我們最大型機器的性能將達到每秒數十億條指令的等級。我們應該始終關注單處理器的絕對性能，因為如果我們能分割問題，可以使用多個處理器來獲得更高的性能。多年來我們已在一些簡單的應用中看到這個概念，例如工作輸入排程程式。因此，一個關鍵的未解決問題是理解如何在全局層面分割給定問題，然後使用平行機器處理其獨立的部分。全局分割是一個非常困難的問題。今天有很多想法，其中一些在特定任務上表現良好，但對於統一的方法還沒有什麼前景看好的。
編譯器技術與機器設計的互動
今天的編譯器技術相當複雜。那些建造機器架構和組織的人應該這樣設計它們，以便已知的編譯器優化技術能夠容易地應用。需要新的編譯器概念來利用新機器的能力。我還相信，現有的優化需要且可能會有額外的改進。更好的暫存器分配就是一個例子。
與通用處理器相比，建造一個性能非常高的專用處理器並不困難。我所說的「專用」，是指浮點單元、快取記憶體和向量處理器等概念。一個建造有快取記憶體和向量單元的機器專門針對那些具有良好快取命中率且易於向量化的問題。它在其他問題上將具有較差的性價比。隨著分割問題進展相對較少以及單處理器速度的明顯限制，我們可能會發現明日的高性能世界與今日差異不大。事實上，將有很大一類問題實際上無法分割，因此將受限於單處理器性能。
我參與過的三個有趣專案
我想向你們介紹我參與過的三個最有趣的專案。它們之所以有趣，是因為我覺得我在這些專案期間學習得比其他時候更快。
Stretch 專案
當我於1956年加入 IBM 時，Stretch 專案正在進行中。專案由 Steve Dunwell 領導，他將性能而非成本置於首位。我的經驗包括編寫一個機器語言是十六進位的 Monte Carlo 模擬程式。令人震驚的是，我在繼續之前沒有寫一個組譯器，但問題是如此有趣，以至於我從未想過這樣做。
為 Los Alamos 設計的 Stretch，其雄心勃勃的目標是比現有的 704 快100倍，同時在定址、浮點運算和非數值運算方面提供極大的靈活性。機器中的任何位元都可以直接定址，任何字都可以被監視，可以參考可變長度資料，浮點數有多種類型。這是一個程式設計師的夢想——尤其是組譯語言級別的程式設計師——對於我們這些設計硬體的人來說是一個極好的挑戰。
為了重疊記憶體存取，我們引入了指令執行前瞻（管線化）。錯誤修正碼（ECC）應用於主記憶體以及磁碟和磁帶 I/O，我們與編譯器開發人員合作開發高效的指令序列和暫存器分配。
用於 704 的 Fortran I 生成了非常優秀的程式碼，即使按今天的標準衡量也是如此。對編譯器感興趣的人從 Fortran 在 Stretch 上的使用中學到了很多。Stretch 架構的許多豐富特性並未被編譯器利用。據我回憶，John Backus 事先告訴我們情況將是這樣。如果當時我們對 Fortran 編譯器了解更多，我們這些架構師會受益匪淺。然而，由於這次以及許多其他經驗，我們了解到，為更簡單的指令集編寫編譯器更容易利用其特性。
雖然 Stretch 在1961年運送給 Los Alamos 時只達到了其性能目標的一半不到，但我們發明並嘗試了許多今天仍在使用的技術。
Advanced Computer System (ACS) 專案
接下來，我想向你們介紹一下 Advanced Computer System (ACS)。這是我們在1964年至1968年間承擔的一個專案。它有一個簡單但令人難以抗拒的目標：設計並建造最快的可行科學電腦。在已故 Jack Bertram 的領導下，我們設計了一台具有許多組織特性，即使在今天也不太為人所知的電腦。然而，由於各種原因，ACS 並未建造。它本來會有一個十奈秒的週期時間，大約是今天價值數百萬美元的電腦的級別，所以它的硬體會非常快。這僅僅是機器組織的起點。在每個週期，我們分派七個運算，一個到分支單元，三個到定點單元，三個到浮點單元。定點單元在每個週期可以啟動三個指令。浮點單元有一個八個運算元的緩衝區，以及從這八個中挑選出前三個已準備好的運算元的邏輯。有兩條通往快取記憶體的路徑，允許每個週期兩次記憶體存取，為了使快取存取時間與 CPU 週期匹配，它採用了五級管線化（這是由於電路整合度低所必需的）。一個巧妙的發明是一個先進先出的儲存佇列，它允許計算繼續進行，而無需等待直寫（store-through），以及一個硬體互鎖機制，用於保護對運算元進行參考時的情況。它也解決了相互干擾的載入指令。
我們的大部分精力都投入到以最小化管線排空的方式處理分支指令。我們將每個分支指令分為其三個基本運算：條件判斷、分支目標位址計算和實際跳轉指令。還有一個分支歷史表，允許根據最近分支指令執行的動態情況進行指令預取。另一種特殊形式的分支稱為「跳過」（skip），它允許編譯器跨分支進行排程。考慮到所有這些硬體輔助，實驗編譯器生成了優秀的程式碼並排程指令以最小化管線效應。
在我們確定硬體設計之前很久，我們就有了一個實驗性的優化編譯器來評估設計的不同變體。與一個由編譯器和硬體人員組成的聯合團隊合作，我學到了不要包含編譯器無法使用的硬體特性，以及包含允許高效編譯的硬體設施的重要性。這個實驗性編譯器是我們後續許多優化演算法工作的來源。今天編譯器中使用的許多程式碼優化方法都源於這項工作。這包括基於區間的控制流分析、資料流分析、公共子表達式消除、程式碼移動、強度削弱和程式碼排程。有時，編譯器能夠為 ACS 生成比最好的手寫程式碼員更好的程式碼。我們了解了高效編譯器及其周邊軟體支援工具的重要性。
20年前建造的 ACS 部分仍然令人印象深刻，除了速度-功耗乘積：內部電路為250皮秒，每個電路功耗約30毫瓦，每個晶片最多有40個電路。如果完整的機器建造出來，我相信週期時間會在十幾奈秒的低端。它在線性代數類型的問題上每個週期可以完成四到五條指令。但是，由於快取延遲以及幾乎總是無法預測正確的分支流，我們在更通用的問題上無法達到接近這個速率。
這僅僅是我們在 ACS 中實現的一些特性。許多想法已經進入 IBM 後續的機器中，特別是在快取記憶體領域。然而，一些更複雜的想法尚未被使用。在許多情況下，這是由於成本與性能的權衡，但我相信成本的下降將使得這些想法得以實現。
ACS 從未走出實驗室；我想它太大太貴了，但對我來說，這可能是我參與過的最令人興奮的專案。回想起來，我認為讓它特別令人興奮的是我們是一個小團隊，大部分由 Jack Bertram 親自挑選，我們開創了專案的各個方面。
我談到了架構和編譯器，但我們一些最巧妙的發明與測試儀器和技術、快速磁碟、封裝和散熱有關。看到我們的工程師處理和解決這些問題，我感到非常滿足。另一個主要因素是團隊的素質。許多名字你們肯定會認得——其中有 Fran Allen, Dick Arnold, Fred Buelow, Phil Dauber, John Earle, Charlie Freiman, Russ Robelen, Herb Schorr, 和 Ed Sussenguth。我對 ACS 唯一的遺憾是，不像編譯器的想法，我們沒有花時間發表我們在硬體方面的想法，以便其他人可以在此基礎上發展。
801 Computer 專案
現在讓我繼續討論我參與的另一個有趣的專案——801 Computer。大約在1974年，我們正在調查建造一個能夠處理大約每小時一百萬次通話的全數位電話交換機的可能性。按每次通話建立約20,000條指令計算，我們估計需要一個每秒執行6百萬條指令（MIPS）的處理器。由於我們對電話了解不多，我們覺得可能應該以一個12 MIPS的處理器為目標。當然，通用機器不是這項任務的最佳選擇。例如，我們有嚴格的即時回應要求。從某種意義上說，我們正在尋找一台專用機器。從一開始，我們還假設我們將用高階語言進行程式設計。在這種情況下，驅動我們的不是絕對性能。我們有一個性能目標。我們知道應用的大致性質；沒有大量的浮點計算，並且正在尋找能滿足這些要求的成本最低的電腦。我們設計了一台機器，後來被稱為 801 Computer。最終，我們放棄了電話交換機的想法，並得出結論，我們在電腦設計方面有一些相當強大的想法。我們用一種高階語言和一個編譯器 PL.8 補充了這些想法，並在接下來的幾年裡繼續進行它們的開發。
801 的主要特性包括獨立的指令和資料快取，提供了記憶體和 CPU 之間更高的頻寬，以及沒有直接對記憶體進行的算術運算，從而極大地簡化了管線化。801 專案的另一個重要部分是硬體和編譯器的緊密耦合和同步開發。這種緊密耦合使得能夠建構一個有效的編譯器並提供了一個簡單的機器組織。
這個專案是一個偉大的團隊努力，我的同事 Marc Auslander, Greg Chaitin, Al Chang, Marty Hopkins, Peter Markstein, 和 George Radin 等等，不僅是偉大的貢獻者，也使整個冒險充滿樂趣。801 專案另一個令人滿意的方面是，我們的許多想法被其他人認為足夠有趣，並在許多大學刺激了大量的額外研究和實驗。Berkeley 對類似的工作創造了「RISC」（精簡指令集計算）這個名稱。
邏輯模擬器機器專案
在 IBM 內部，我們認為對新機器的硬體進行廣泛模擬極其重要。隨著機器複雜性的增加，模擬它們所需的時間變得太長了。在1980年，我們開始開發一台專用機器來完成這項任務。Rick Maim 開發了一個早期原型，Monty Denneau 設計、建造並除錯了一個非常龐大的系統。其目標是為邏輯設計模擬提供硬體輔助，根據要模擬的電路數量，將模擬速度提高100倍到1000倍。邏輯模擬似乎是平行機器的理想問題，因為它應該簡單地模擬電腦實際工作的方式。這台機器有256個平行邏輯單元存取共享記憶體。一個特殊的編譯器接收一個相當高階的邏輯描述，生成必要的指令，並將它們載入到機器中。每個單元按順序模擬大約4000個電路，並在每個週期結束時，通過一個無阻塞開關將其結果廣播給其餘255個夥伴。因此，每個週期模擬256個電路。
將邏輯塊分配給機器類似於將電路分配給晶片，根據 Rent's Law，4000個電路對應4000個 I/O 應該綽綽有餘。儘管如此，編譯器的分割問題在大型主機 CPU 上需要很長時間。這迫使我們只能將這些機器用於長時間運行的模擬。儘管存在這個耗時的困難，許多這樣的機器在 IBM 持續使用。具有更高交換能力的下一代邏輯模擬器正在建造中，以緩解這個問題。
然而，請注意，無阻塞開關的增長速度至少與 N*logN 一樣快，而機器硬體則呈線性增長。因此，在極限情況下，它將全部是交換器。我提到這個例子是因為它簡單地演示了一個悖論：從先驗來看，將邏輯模擬器映射到多台機器上似乎非常自然和簡單，但一個簡單直接的擴展將會遇到困難。
未來展望
這將我帶到了未來。利用電路和記憶體密度的改進（例如，一百萬個電體管的晶片和四兆位元的晶片），僅用幾片 CMOS 晶片就可以建造一台強大的科學機器，它在許多重要問題上將與基於向量的電腦性能相媲美。這台機器將在單個晶片上擁有一個非常快速的帶緩衝區的浮點乘加單元。它也能夠同時執行一個定點、一個浮點和一個分支指令。如前所述，優化編譯器對於利用這些機器至關重要。
記憶體便宜且成本改進將持續。因此，預期將有包含數百吉位元組的大容量隨機存取記憶體。磁碟將維護備份資料庫，但通過分頁，資料庫應用程式將從主記憶體執行，速度比今天快得多。這的重要性在於，為在機械裝置上實現高性能而投入的巨大努力將不再必要。
It is this trend that emphasizes cost over performance that leads me to believe the search for future scientific computing performance has to concentrate on gross parallelism.
正如我之前說過的，我預計這三十年來電腦性能提高100倍、成本降低10,000倍的趨勢將會持續下去。正是這種強調成本而非性能的趨勢，使我相信未來科學計算性能的探索必須集中在大規模平行性上。由於降低週期時間和每條指令週期數越來越困難，這是必要的。由於成本持續急劇下降，將可以匯聚許多 CPU 同時執行多個指令流。主要挑戰將在於編譯器優化技術，既要識別平行性，也要排程指令。一個特別困難但至關重要的問題是最小化這些平行處理器中的快取未命中。例如，在一個內部迴圈每週期執行三條指令的機器上，如果快取未命中需要10個週期，那麼3%的未命中率將使性能減半。
因此，像這樣的機器可以被認為是專用的，因為快取命中率高的問題能夠實現高性能。我看到了許多巧妙程式設計可以大幅提高快取命中率的技術。我相信對編譯器感興趣的人應該努力使這些巧妙技術自動化，就像編譯器已經將向量化自動化一樣。
我之前提到，改進的演算法可以提供最大的槓桿效應，是問題維度上的量級變化，而平行性最多只能提供與處理器數量成線性的加速。為此類平行機器量身定制、利用其架構和互連巧妙細節的新演算法將至關重要；相反地，面向此類平行演算法的專用機器將成為可能且經濟上合理。
關於機器比較的困難
許多年前，John McCarthy 曾對我說，如果不是因為 Alan Turing 和他關於通用機器的想法，我們至今可能仍在爭論不同機器設計的能力。幸運的是，這不是一個問題；然而，我們似乎確實對各種機器設計的性價比爭論不休。爭論因每台機器都能展示一組它專門擅長的問題和演算法而變得更加複雜。我確信對於平行機器來說情況會更糟，因為其專用化程度可能更高。今天，對各種機器架構的比較做得不夠好，也許是因為其固有的困難，也許是因為商業影響。希望未來能做得更仔細；也許我們可以向學術界尋求幫助。
結論
我想重申，過去三十年來，人們強調的是成本改善而非性能。我認為沒有理由這個趨勢不會繼續下去。展望未來，我們看到單處理器的性能正接近極限，因此，我們看到許多人正在研究多機聚合體。由於這是否能解決高性能科學計算問題尚不明確，我們不應推斷未來僅僅是今日想法的簡單外推。我並不因為似乎沒有通往高性能的明確途徑而感到沮喪。我覺得電腦的靈活性將使我們能夠以尚未設想的方式解決問題，這將使計算的未來比過去更加有趣。