Braid computing: achieving OOO performance with in-order complexity

這張照片是今天下午四點左右在樓頂照的，晴空萬里的藍天讓人心情舒暢，但是和接下來的本文內容完全無關，放上來只是讓充滿文字的版面不要那麼無聊罷了XD

ISCAS 2008的論文，由德州大學(UT at Austin)的Francis Tseng和Yale N. Patt發表。這篇論文的賣點在標題就很聳動的寫出來：以循序處理器的硬體複雜度得到亂序處理器的效能。亂序執行(out-of-order execution, OOOE)技術有機會大幅提高運算效能(請注意，是有機會，不是一定，大部份case裡提高的是耗電量...)，但是硬體複雜度太高，耗電量更是驚人，以至於4向以上的亂序處理器從來沒有被商品化，只在學術論文上出現。

本篇論文的賣點在於作者們強調，用他們的braid概念來實現硬體的話，有機會用很低的硬體複雜度，也就是跟循序處理器一樣的複雜度實現亂序處理器的效能。當然天下沒有白吃的午餐，代價是軟體也要跟著修改，這裡的修改不需要你重新編譯程式(原作者有指出, 如果可以重編的話效果會更好)，但是需要讓原本的程式碼被拿來作分析，找出內部braid的分佈，同時把一些braid相關的註記加進程式碼，所以修改後的指令格式會和原來有點小差異，造成整個執行檔的內容都不一樣了。聽起來很嚴重，其實還好，嗯，好吧，其實蠻嚴重的…雖然不用重新編譯程式，但是這意味著哪天這顆cpu商品化的話，你升級了cpu之後還要連代更新硬碟裡包括os在內的所有程式，網路上抓下來的軟體也沒辦法馬上執行，要經過一次「翻譯」才能用。

為什麼這麼嚴重，我還說他「還好」? 因為他作的修改是以基本區塊(basic block)為界限，只會更動基本區塊內部的指令順序，對於不同的區塊之間的前後排列順序以及區塊大小(區塊大小意謂著區塊內指令的多寡)都沒有變動，所以並沒有更動程式內部指令的邏輯順序，只是會根據分析的結論，重新安排指令在區塊內的排列順序。這樣的重排不會影響到跳躍指令(有人翻作「分支指令」，branch)的行為，因為總指令個數，和所有的進入點(entry point,跳躍指令的目標位址)的相對位址並沒有改變，對記憶體存取的load/store指令的先後次序也被小心的保留下來，整個「修改」程式的動作就是類似把 ABCDE的指令順序改成 BDCAE(當然這樣的修改順序以不影響程式邏輯為原則)，然後把分析得到的一些結果也記入指令格式，變成bdcae的最終型態。