[go: up one dir, main page]

TW200903339A - Parallelizing sequential frameworks using transactions - Google Patents

Parallelizing sequential frameworks using transactions Download PDF

Info

Publication number
TW200903339A
TW200903339A TW097118420A TW97118420A TW200903339A TW 200903339 A TW200903339 A TW 200903339A TW 097118420 A TW097118420 A TW 097118420A TW 97118420 A TW97118420 A TW 97118420A TW 200903339 A TW200903339 A TW 200903339A
Authority
TW
Taiwan
Prior art keywords
loop
transaction
parallel
transactions
commitment
Prior art date
Application number
TW097118420A
Other languages
English (en)
Other versions
TWI451340B (zh
Inventor
John Joseph Duffy
Yosseff Levanoni
Jan Gray
Original Assignee
Microsoft Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Microsoft Corp filed Critical Microsoft Corp
Publication of TW200903339A publication Critical patent/TW200903339A/zh
Application granted granted Critical
Publication of TWI451340B publication Critical patent/TWI451340B/zh

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/466—Transaction processing
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
    • G06F8/456—Parallelism detection
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/466—Transaction processing
    • G06F9/467—Transactional memory

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Advance Control (AREA)
  • Devices For Executing Special Programs (AREA)

Description

200903339 九、發明說明： 【發明所屬之技術領域】 本發明係有關於使用交易以平行化循序框架之方法。 【先前技術】 软體交易記憶體（software transactional memory, STM) 是一種並行控制機制’其近似於以並行計算之方式來控制 對共享記憶體存取的資料庫交易。在交易記憶體之内容中 的父易是為一套程式碼’其執行一系列的讀取及寫入動作 以共享記憶體。STM被當作傳統鎖定機制的替代方式來使 用。程式設計師將一宣告註解（例如基元）繞著一程式碼區 塊放置，以指示他們所需之安全性質’且該系統自動地保 證此區塊會以基元方式執行關於其他的受保護程式碼區 域。該軟體交易記憶體程式模組能避免鎖定式的優先反向 (Priority Inversion)以及死鎖（deadlock)問題。 同時典塑的STM系統具有許多優點，其仍需要程式設 計師能小心的避免非故意的記憶體存取排序。例如，在— 典型STM環境中承諾（commit) 了交易（亦即承諾處理）的 順序是不被約束的。交易與另一者競赛以承諾的意義，代 表無論交易1在交易2之前承諾或是在之後承諾，其通常 是該程式之動態排程的一乘積（且通常亦是經由程式特定 之邏輯）。此外，若兩交易衝突，像是由於嘗試寫入到相同 部分之記憶體之故’則他們的承諾順序可基於許多可能競 爭管理政策的其中之一而被任意地選擇。在此些方案之兩 5 200903339 者中’並未保證了特定承諾順序；因此責任是在程式 師身上’他/她要負責其程式能以任一順序來正確 作。這使得平行程式化變的非常困難。 一種執行順序很重要且平行性是非常具有吸引力 案’是發生以平行方式執行一迴圈的多個迭代時。採 個經典的for…each迴圈之範例來說明，如下所示：
ForEach(string s in List<string>) { S； 在該迴圈的各個迭代期間，將會執行在該迴圈之 内的該陳述式S。此一迴圈曾被寫成能循序地執行， 該迴圈之第—迭代在該第二迭代開始之前結束，然後 類推。若此—循序迴圈以平行方式執行，而沒有額外 防措施來處理可能的副作用（side effects)或順序相依 則可能會發生無法預測的結果。 【發明内容】 兹揭示了各種科技與技術以用於將在一交易記憶 統中之交易予以排序。茲提供一特徵給一交易記憶體 以允許一預先決定（pre_determined)承諾順序該順序 對複數個交易而所指定。該預先決定承諾順序在運行 用來幫助決定一在該交易記憶體系統中承諾該等交易 序在—實作中’該預先決定承諾順序可被整體的排 設計 地工 的方 用一 主體 其中 以此 的預 性， 體系 系統 係針 時被 的順 序.或 6 200903339 是部分的排序。假設是整體排序，該等交易被迫已一線性 順序來承諾。假設是部分排序，則該等交易被允許能以多 個可接受方案其中之一的方式來承諾。在一實作中，一承 諾仲裁器（arbitrator)保持對次個承諾（next-to-commit)值 的追蹤，該值代表應該被允許於次個承諾的交易，且當一 特定交易準備好承諾時，若其承諾順序數目與該承諾仲裁 器的次個承諾值相符，則其被允許進行承諾。
當一衝突發生在一第一交易及一第二交易之間時，則 引動（invoke) —競爭管理處理。該預先決定交易順序被用 於該競爭管理處理中以幫助決定是該第一交易或是該第二 交易應該贏得該衝突並被允許進行處理。 茲揭示一種用於將一循序迴圈轉換成一平行迴圈以用 於一交易記憶體系統的技術。並提供一種以交易記憶體為 基礎之系統。程式碼之第一區段（其含有一原始的循序迴圈） 被轉換成程式碼之第二區段（其含有一平行迴圈），其使用 交易以保留一原始輸入對輸出的對映並增進安全性。例 如，可採用該原始循序迴圈之各迭代並產生一跟隨一預先 決定承諾順序處理之分離交易，以將該原始循序迴圈轉換 成一平行迴圈，且然後將該等交易分派給不同執行緒，使 得他們能以平行方式執行。當正執行該平行迴圈時，應可 從一特定交易内偵測出一未處置異常，由該特定交易以及 任何前導子交易所完成的狀態修改被承諾，且由任何後續 者交易所完成的狀態修改被放棄。否則，所有的交易皆承 諾。 7 200903339 在一實作中，開路端及/或閉路端循序迴圈可被轉換 成平行迴圈。例如，將程式碼之一區段（其含有一原始循序 迴圈）予以分析，以決定該原始循序迴圈之迭代固定數目。 該原始循序迴圈被轉換成一平行迴圈，其可產生最多可達 到迭代固定數目的交易數量。如另一範例般，一開路端循 序迴圈可被轉換成一平行迴圈，其可產生一分離交易，該 分離交易含有一用於一推測管線之各迭代的個別工作項 目。此些交易被分派給不同執行緒以允許至少部分的平行 迴圈能以平行方式執行。然後，在受益於預先決定承諾排 序的優點下，在該交易記憶體系統的保護下執行該平行迴 圈。 在一實作中，茲提供一種用於執行一平行迴圈的方 法，該平行迴圈係從一開路端循序迴圈處所產生。茲產生 一推測管線，其估測一定數目之迭代以在一平行迴圈中執 行，該平行迴圈係從一開路端循序迴圈處所產生。該系統 採用該推測管線之各迭代並產生一含有一個別工作項目之 分離交易。此些分離交易則被分派至不同執行緒，各他們 能在以平行方式執行時停止。茲針對個別工作項目各者評 估一終止狀態。當該等個別工作項目之特定一者決定要終 止該平行迴圈的時間已經來到，則該等前導子被承諾並放 棄該等後續者。 本發明内容係提供以依簡化形式來介紹概念之選擇， 本發明將在實施方式中進一步描述。此發明内容無意於確 定申請專利範圍標的之關鍵特徵或基本特徵，亦無意於用 8
200903339 以限制申請專利範圍標的之範疇。 【實施方式】 為了促進對本發明原理的了解之目的，將參考圖 所示具體實施例並使用特定表達方式來描述之。然而 了解的是，本發明之範疇不因此所受限。於所述之具 施例的任何改變及進一步的修改及如此處所述之原理 一步應用之考量對於熟習此項技術者而言為經常發生 該系統在一般内容中可被描述為一交易記憶體系 但是該系統亦能作為除此之外的其他目的之用。在一 中，在此所述之一或更多技術可被實作成在一框架程 的一特徵，像是 MICROSOFT® .NET Framework，或 自任何其他類型的程式或服務，其能提供平台給開發 以開發軟體應用程式。在另一實作中，在此所述之一 多技術被實作成其他應用程式之特徵，該等應用程式 理關於開發出在並行環境中執行之應用程式。 在一實作中，茲提供在該交易記憶體系統中之 徵，以允許一預先決定承諾順序，該順序係針對複數 易而所指定。在一實作中，當一衝突發生在一第一交 一第二交易之間時，則引動（invoke)—競爭管理處理 預先決定交易順序則被用於該競爭管理處理中以幫助 是該第一交易或是該第二交易應該赢得該衝突並被允 行處理。 在另一實作中，茲提供在該交易記憶體系統中之 式中 ，應 體實 的進 的。 統， 實作 式内 是來 人員 或更 係處 一特 個交 易及 。該 決定 許進 一特 9
200903339 徵，以將一原始循序迴圈轉換成一平行迴圈。該 迴圈被轉換成一平行迴圈，其所用方式是確保該 對該輸出的對映會被保留。在此所用之用語「該 對該輸出的對映會被保留」，意味著在執行經平行 後該程式的狀態，會與若已運行該循序迴圈的狀 在一實作中，該原始輸入對該輸出的對映會藉由 序列迴圈之各迭代放置到一交易中的方式，而被 平行迴圈中，且然後使用在此所述之預先決定承 理，以確保該等交易能以適當順序承諾。 同時在此討論之許多範例在一般内容中可被 軟體交易記憶體系統，將會了解到在其他實作中 論之部分、全部或額外的特徵及/或技術可用一 記憶體系統，以與一軟體交易系統分離或是合併 實現。 如第1圖所示，一示範性電腦系統係用來實 之一或更多部分，其包括一計算裝置，像是計算身 在其最基本的組態中，計算裝置100通常包括至 單元1 02以及記憶體1 04。根據運算系統1 00之 及種類，記憶體1 04可為揮發性（例如RAM )、 (例如ROM、快閃記憶體等）、或二者的某種組 圖中以虛線1 0 6標示上述最基本之組態。 除此之外，運算系統1 0 0亦可具有額外的特 舉例而言，運算系統1 0 0亦可包含額外儲存裝置 式和/或非可移除式）包括但不限於，磁碟片、磁 原始彳盾序 原始輸入 原始輸入 化迴圈之 態相同。 將該原始 保留在該 論順序處 描述為一 ，在此討 硬體交易 的方式來 現該系統 t 置 1 00。 少一處理 實際組態 非揮發性 合。第1 徵/功能。 (可移除 帶 '或光 10 200903339 碟片。第1圖巾，以可移除式 儲存裝置"。來表示此類額外…】3:及非可移除式 括以任何方法或技術實作可用以儲存二電腦儲存媒體包 性記憶體、可移除及非可移 訊之揮^丨生及不變 讀取指令、資料結他上述資關如電腦可 可移除式儲存裝置⑽、以可料記憶體1〇4、 上述電腦儲存媒體之實施例;;存裝£ 110皆為 RAM、ROM、EEPROM、快閃吃情 °己隐體或其他記憶體技術、 CD-ROM、數位多功能影音 ^ 九碟（DVD )或其他光學儲存 媒體、磁匣、磁帶、磁碟儲 存或其他磁性儲存裝置、或能 夠用以儲存所需資訊且 '、電腦系統存取之任何其他媒 體。任何上述電腦儲存姐 媒體皆可作為裝置100的一部份。 裝置100亦可包括— 或更夕的通訊連接114，其可允 許計算裝置100與其他的 电細/應用程式115進行通訊。 裝置100亦可具有輸入裝 衣置（們）1 12，例如鍵盤、滑鼠、 筆、語音輸入裝置、觸控給 佐输入裝置、相機等等。亦可包括 輸出裝置（們）111例如顯千g 斯顯不益、擴音器、印表機等。上 述裝置皆為相關領域所熟如，不需於此處資述。 繼續參考第1圖的情況下，現在來到了第2圖，其說 月了#運作在计介裝^ 1〇〇上的交易記憶體應用程式 2 00交胃。己隱體應用矛里式2〇〇係駐存在計算裝置⑽上的 該等應用程式其中之-。然而，吾人將了解到交易記憶體 應用程式可替代地或額外地在-或更多電腦及/或在如第 1 圖内所示的不同變.各I „ I化中’破具體實施成電腦可執行指 11
200903339 令。替代地或額外地，交易記憶體應用程式2 0 0的一或 多部分可成為系統記憶體1 04的一部份、可在其他電腦 電腦/應用程式115上，或可為出現在電腦軟體領域中 一態樣的其他此類變化。 交易記憶體應用程式2 0 0包括程式邏輯2 0 4，其係 責實行某些或全部在此所述之技術。程式邏輯204包括 於提供一交易記憶體系統（STM)的邏輯206;用於提供一 諾仲裁器的邏輯2 0 8，該承諾仲裁器允許一預先決定承 順序能被以靜態或動態地方式針對在該 STM系統中的 數個交易而指定；用於允許該承諾仲裁器之邏輯210, 讓該承諾仲裁器能使用該預先決定承諾順序以在運行時 助決定一在該交易記憶體系統中承諾該等交易的順序； 於提供一競爭管理處理之邏輯212，其當一衝突發生在 第一交易及一第二交易之間時，則引動該競爭管理處理 用於在該競爭管理處理中使用該預先決定承諾順序的邏 214,以幫助決定是該第一交易或該第二交易應該赢得該 突並被允許繼續進行（例如需視在相同交易群組中之 兩個交易，哪一個具有較低的承諾順序數目而定）；用於 許該承諾仲裁器可運作以使用該預先決定承諾順序的邏 2 1 6，該預先決定承諾順序係排序以追蹤一或更多的排序 (例如在整體排序中——代表複數個交易中之次個交易 次個承諾欄位應被允許用來承諾），且該邏輯2 1 6能用於 該一或更多排序值拿來跟一給定交易之特定承諾順序數 做比較，以觀察是否該給定交易之承諾是被適當的給予 更 的 之 負 用 承 諾 複 以 幫 用 輯 衝 這 允 輯 值 的 將 a 了 12
200903339 應執行的排序；以及其他能用於運作該應用 220。在一實作中，程式邏輯204可運作以從另 計劃性地呼叫，像是對一在程式邏輯204中之 —呼口 〇 繼續參考第1及第2圖的情況下，現在來 1 0圖，該等用於實現一或更多交易記憶體應用 實作的階段（stages)，在此會做更進一步的詳細 種形式中，第3圖的處理為至少部分地實現在言十 之作業邏輯中。該程序開始於起始點2 4 0並提 憶體系統（例如一軟體交易記憶體系統）（階段 供一特徵以允許一預先決定承諾順序（例如 一 部分排序）以針對複數個交易來指定（例如以 的方式來分派）（階段2 4 4)。在此所用之該術語 承諾順序」意指包括了一特定順序，其中相關 定群組應被承諾，同時在該等交易開始運行之 間點來決定該特定順序。在此所用之該術語「 由該相同承諾仲裁器所管理之交易的一特定集 數個），以及那些交易的巢狀子代。 該預先決定承諾順序係用於運行時以幫助 易記憶體系統中承諾複數個交易的一順序（階ΐ 預先決定承諾順序被用來幫助解決發生在二或 個交易間的衝突（階段2 4 8)。該處理程序會在 處終止。 第4圖說明牽涉到使用一承諾仲裁器以強 程式之邏輯 一程式處被 程序使用單 到了第3到 程式200之 描述。在一 •算裝置100 供一交易記 242)。茲提 整體排序或 動態或靜態 「預先決定 交易之一特 前在任何時 群組」包括 合（例如複 決定在該交 246)。該 更多支付數 結束點 250 制執行一預 13 200903339 先決定承諾順序的該等階段的一實作。在一形式中，第4 圖之處理程序是至少部分地實現在計算裝置100之作業邏 輯中。該程序開始於起始點270並提供一用於交易記憶體 系統的一或更多承諾仲裁器，該承諾仲裁器町運作以允許 一預先決定承諾順序能針對複數個交易來指定（階段 272)。在此所用之該術語「承諾仲裁器」是意味著包括任 何類型的程式、特徵、或處理’其係負責負責管理交易之 一或更多群組’該等群組應該與彼此相互排序。在一實作 中’可有一或更多的承諾仲裁器在一程式中於任何給定時 間啟動。例如’可建立如所需般的許多承諾仲裁器，以管 理父易之不同群組。該承諾仲裁器追蹤並更新一或更多的 排序值’該等排序值被用於決定與交易彼此相關的適當排 序（階段2 7 4)。在整體排序的情況下，一次個承諾欄位可 被用來表現複數個交易中的次個交易，該次個交易應於下 次被承諾（階段2 7 4)。在部分排序的情況下，不同可能順 序的導向圖形能使用該等排序值來追蹤。適當地，該承諾 仲裁器使用該預先決定承諾順序，以對複數個交易各者提 供一承諾順序數目（階段276)。 當複數個交易之一特定交易準備承諾時，若用於該特 定交易之該承諾順序數目在拿來與—或更多之排序值進行 比較之時顯示了該承諾為適當的，則該承諾仲裁器 交易進行承諾（階段278)。在整體排序的情況下，此^案 發生在當次個承諾攔位以及用於該特定交易之該承諾順序 數目具有相同&。在此—方案中，若該承諾是成功的，則 14 200903339
該承諾仲裁器允許該交易進行承諾並然後將該次個承諾欄 位按順序增量至次個數目（例如次個較高數目）（階段 278)。當複數個交易之該特定交易準備要承諾時，若用於 該特定交易之該承諾順序數目在拿來與該等排序值進行比 較之時顯示了該承諾並非適當，則該特定交易被放置在一 保持模式（h ο 1 d m o d e)直到該特定交易在一較晚時間點（於 一前導子（predecessor)交易承諾之後）被喚醒（階段280)。 在整體排序的情況下，當該次個承諾欄位以及用於該特定 交易之順序數目不具有相同值的時候，則輸入此保持模式。 在一實作中，該系統可在其直系前導子已承諾之後喚 醒一交易，而在這種情況下其會嘗試立刻地承諾。替代地， 該系統可選擇在某些非直系前導子已承諾之後才喚醒一交 易，即使其直系前導子或尚未承諾。在被喚醒後，該系統 檢查以觀看對該交易而言真的進行承諾是否適當。若是， 則承諾該交易。該處理會在結束點2 8 2終止。 第5圖說明牽涉到使用一承諾仲裁器以強制執行複數 個交易之整體排序的該等階段的一實作。在一形式中，第 5圖之處理程序是至少部分地實現在計算裝置1 00之作業 邏輯中。該程序開始於起始點290並提供一用於交易記憶 體系統的一或更多承諾仲裁器，該承諾仲裁器可運作以允 許一預先決定整體排序能針對複數個交易來指定（例如指 定一確切順序的步驟，其中應承諾該等複數個交易）（階段 292)。當該等複數個交易之一特定交易達到其承諾點時， 為了強制執行該承諾順序，該特定交易之承諾順序會被與 15 200903339 該承諾仲裁器之次個承諾欄位作比較（階段 2 9 6)。在一實 作中，若該系統決定該整體排序之強制執行並非必要（例如 像是因為能很肯定沒有衝突發生），則該整體排序需求可適 當地中斷（階段 2 9 4 )，然後該處理在結束點3 0 2處終止。
若承諾排序正待被強制執行，且若該特定交易之承諾 排序具有與該承諾仲裁器之次個承諾欄位相同的（選擇點 296)，則承諾該特定交易，且若該承諾是成功的，則增量 該次個承诺欄位並喚醒該次個後續者（s u c c e s s 〇 r)(若有任 何後續者存在的話）（階段2 9 8)。若該特定交易之承諾順序 不具有與該承諾仲裁器之次個承諾欄位相同的值（選擇點 2 9 6 )，然後該特定交易係處在保持/休眠模式，直到該特 定交易在一較晚時間點（於一前導子交易承諾之後）被喚醒 (階段3 00)。在一實作中，在較晚的時間點處，若一衝突 發生在一前導子，則可要求該特定交易取消並回捲 (rollback)，使得一前導子可向前進展。否則，若未有此類 衝突發生，則一旦能滿足載此所述之該承諾順序需求，該 特定交易應能夠完成承諾。然後該處理在結束點3 0 2終止。 第6圖說明牽涉到使用一承諾仲裁器以強制執行複數 個交易之部分排序的該等階段的一實作。在一形式中，第 6圖之處理程序是至少部分地實現在計算裝置1 0 0之作業 邏輯中。該程序開始於起始點3 1 0並提供一用於交易記憶 體系統的一或更多承諾仲裁器，該承諾仲裁器可運作以允 許一預先決定部分排序能針對複數個交易來指定（例如指 定複數個可接受順序的步驟，其中應承諾該等複數個交 16 200903339 易）（階段3 1 2)。當該等複數個交易之一特定交易達到其承 諾點時，為了強制執行該承諾順序，該等前導子交易之狀 態（例如一或更多排序值）會對該特定承諾交易做諸詢（例 如由該承諾仲裁器所追蹤）（階段 3 1 4)。若所有對於該特 定交易的前導子皆已承諾（選擇點 3 1 6 )，則承諾該特定交 易（階段3 1 8)。若該承諾是成功的，由該承諾仲裁器所追 蹤之一或更多值會被適當地更新，且會喚醒所有可能的次 個後續者（若有任何後續者存在的話）（階段3 1 8)。
若所有對於該特定交易的前導子尚未承諾（選擇點 3 1 6) 5則該特定父易係處在保持/休眠权式 > 直到該特定 交易在一較晚時間點（於一前導子交易承諾之後）被喚醒 (階段 320)。該處理在結束點322處終止。 第7圖說明牵涉到提供一負責管理衝突（其係使用該 預先決定承諾順序資訊）之競爭管理處理的該等階段的一 實作。在一形式中，第7圖之處理程序是至少部分地實現 在計算裝置100之作業邏輯中。該程序開始於起始點340 並提供一交易記憶體系統，其支援一用於一或更多交易群 組的預先決定承諾順序（階段 3 4 2)。茲提供一競爭管理處 理，其係在一衝突發生於一第一交易以及一第二交易之間 時所引動（階段 3 44)。該預先決定承諾順序被用在該競爭 管理處理中，以幫助決定是該第一交易或該第二交易應該 贏得該衝突並被允許進行處理（階段 3 4 6)。若該第一交易 及該第二交易非屬該相同交易群組的一部份（選擇點 3 4 8 )，則不會在此兩個交易之間強制執行一預先決定承諾 17 200903339 順序（因為並不存在）（階段 3 5 0)。按此一方案，因為 個交易不屬於相同的交易群組，則該排序因素不會被 . 幫助解決該衝突（階段 3 5 0)。 若該第一交易以及該第二交易屬於該相同交易群 一部份（選擇點 3 4 8 )，則該系統對該第一交易之第一 數目以及該第二交易之第二順序數目進行比較（ 3 5 2)。具有較低順序數目的該交易被允許進行（或是要 另一適合的優先權排序）（階段3 5 4)。該處理在結束點 1 ' 處終止。 第8圖說明牽涉到提供一負責管理巢狀交易之 (其係使用該預先決定承諾順序資訊）之競爭管理處理 等階段的一實作。在一形式中，第8圖之處理程序是 部分地實現在計算裝置100之作業邏輯中。在一實作 整體的上代鍊（ancestor chain)在承諾該特定交易之前 對各個交易所考慮，故任何在該鍊中所呈現的排序都 制執行。該程序開始於起始點 3 7 0並提供一競爭管 理，其係在一衝突發生於一第一交易以及一第二交易 (, 時所引動（階段 3 72)。一預先決定承諾順序被用於該 管理處理中，以幫助決定是該第一交易或該第二交易 赢得該衝突並被允許進行處理（階段 3 72)。若該第一 二交易非屬該相同交易群組的一部份（選擇點 3 76)， " 會在此兩個交易之間強制執行一預先決定承諾順序（ 並不存在）（階段 3 7 8)且該處理在結束點3 8 8處終止。 第一交易以及該第二交易屬於該相同交易群組的一 該兩 用來 組的 順序 階段 具有 356 衝突 的該 至少 中， 係針 被強 理處 之間 競爭 應該 及第 則不 因為 若該 部份 18 200903339 (選擇點3 7 6)，則該系統檢查以觀看是否有包含該巢狀交 易（選擇點 3 80)。 若未包含巢狀交易（選擇點 3 8 0 )，則該第一交易的順 序數目（或其他排序指示符）被拿來與該第一交易的順序數 目（或其他排序指示符）做比較（階段 3 8 4)。具有較低順序 數目的該交易被允許進行（或藉由使用其他適合的排序準 則，來按順序決定次個交易）（階段 3 8 6)。
若包含巢狀交易（選擇點3 8 0 )，則該第一交易之頂層 上代的順序數目（或其他排序指示符）被拿來與該第二交易 之頂層上代的順序數目（或其他排序指示符）（階段 3 8 2)做 比較。在此所用之該術語「頂層上代」（top level ancestor) 是意指包括了共同上代的直系子代（其中包含共同上代）， 以及各交易之頂層上代（其中未包含共同上代）。此些包含 共同以及非共同上代的方案會在第9與第10圖中更進一步 的詳細說明。具有較低順序數目的該交易被允許進行（例如 相關於曾具有較低順序數目或其他適合準則之上代的交 易）（階段3 86)。該處理在結束點3 8 8處終止。 第9圖是一邏輯圖，係說明一具有頂層上代（其具有一 共同上代）的示範性上代樹。在所示範例中，交易 A為D 及E的共同上代。發生在D與E之間的衝突中，交易B及 C的順序數目（共同上代A的直系子代）係分析以決定是交 易D或是E應該被允許進行（在第8圖中的階段3 82)。
第10圖是一邏輯圖，係說明一具有頂層上代（其不具 有一共同上代）的示範性上代樹。在所示範例中，交易 A 19
200903339 為交易C的上代。交易D為交易F的上代。發生在C 之間的衝突中，則交易A及D (個別的頂層上代）的順 目被拿來比較以決定是交易C或是F應該被允許進；f 第8圖中的階段3 82)。 第1 1圖說明牽涉到藉由使用一在一交易記憶體 中之承諾仲裁器來減少工作浪費量的該等階段之 作。。在一形式中，第1 1圖之處理程序是至少部分地 在計算裝置1 〇 〇之作業邏輯中。該程序開始於起始點 並提供一或更多用於一交易記憶體系統的承諾仲裁器 承諾仲裁器可運作以允許一預先決定承諾順序能針對 個交易所指定（階段 402)。該承諾仲裁器可運作以讓 易處於休眠/保持模式，以阻斷該交易在一前導子仍 行時重新執行（例如藉由分析該預先決定承諾順序以 該適當順序）（階段 4 04)。該承諾仲裁器亦可運作以在 該（等）前導子交易已結束之情形下，喚醒曾處於保持 的交易（例如藉由再次分析該預先決定承諾順序以決 適當順序）（階段4 0 6)。藉由提供此些阻斷及喚醒步驟 承諾仲裁器能透過避免該等運作被執行（故不必於稍 成該等運作）的方式，來幫助減少浪費的工作量（ 4 0 8)。該處理在結束點4 1 0處終止。 第12圖說明牽涉到分析在一競爭管理處理中之 體上代鍊以決定適當衝突解決方案的該等階段之一實 在一形式中，第1 2圖之處理程序是至少部分地實現在 裝置100之作業邏輯中。該程序開始於起始點430並 與F 序數 亍（在 系統 一實 實現 400 ，該 複數 一交 正執 決定 一旦 狀態 定該 ，該 後完 階段 一整 作。 計算 提供 20
200903339 一競爭管理處理，其在一衝突發生於一第一 交易之間時而被引動（階段 432)。一預先決 用於該競爭管理處理中以幫助決定是該第一 二交易應該赢得該衝突並被允許進行處理〇 預先決定承諾順序的整體上代鍊是經分析以 當衝突管理（階段 4 3 6)。例如，若是有四個 親代兩個是子代，其中B是巢套於A内而 内。假設在A及C之間有一排序關係，其 之前承諾。若B與D衝突，該競爭管理處理 為偏好於D是無助於給予A必須於C之前； 段4 3 6)。該處理在結束點4 3 8處終止。 繼續參考第1圖的情況下，現在來到了 明了一種具有平行迴圈支援（其運作於計算 的交易記憶體應用程式5 0 0。在一實作中， 支援之交易記憶體應用程式5 0 0是駐存在計 之該等應用程式之一。然而，吾人將了解到 支援之交易記憶體應用程式5 0 0可替代地或 實施成在一或更多電腦上及/或不同於第1 各種變化上的電腦可執行指令。替代地或額 行迴圈支援之交易記憶體應用程式5 0 0的一 為系統記憶體1 04的一部份、可在其他電腦 程式1 1 5上，或可為出現在電腦軟體領域中 他此類變化。 具有平行迴圈支援之交易記憶體應用程 交易與一第二 定承諾順序被 交易或是該第 皆段 434)。 一 幫助決定該適 交易，兩個是 D是巢套於C 中A應該於C 應該偏好B因 表諾的結果（階 第13圖，茲說 裝置100上） 具有平行迴圈 算裝置100上 具有平行迴圈 額外地被具體 圖所示範例之 外地，具有平 或更多部分可 的電腦/應用 之一態樣的其 式5 0 0包括程 21
200903339 式邏輯 5 04，其係負責實行某些或全部在此所述之技 程式邏輯 504 包括用於提供一交易記憶體系統的 5 0 6;用於將程式碼之第一區段轉換成程式瑪之第二區 邏輯 508，該第一區段含有一原始的循序迴圈，而該 區段含有一平行迴圈，其使用交易以保留一原始輸入 出的對映並增進安全性；用於將原始循序迴圈之一或 迭代放置到在該平行迴圈之該等交易中之一個別交易 輯5 1 0 ;藉由使用一預先決定承諾順序來承諾該等交 方式，而用於保留一原始輸入對輸出之對映的邏輯 5 該預先決定承諾順序是與該原始循序迴圈512之執行 相符；用於使用一承諾仲裁器之邏輯 5 1 4，其作用為 原始循序迴圈含有能修改資料之運作，則能偵測並處 該平行迴圈中之衝突；用於產生程式碼之第二區段之 5 1 5，其無須執行該原始循序迴圈之一編譯器分析；用 立程式碼之第二區段的邏輯 5 1 6，其係採用允許該等 能按一順序來承諾的方式所建立，若決定該原始循序 能免於重新排序（使用啟發式、在程式碼之第一區段中 用者定義式之注釋等等），則該順序不需依賴該原始循 圈之一執行順序；用於產生程式碼之第二區段的 5 1 7，故某些交易能以平行方式被執行；使用該交易記 系統以執行程式碼之第二區段的邏輯 5 1 8，其中至少 的分離交易正在不同執行緒（thread)上執行；以及其他 於運作該應用程式之邏輯520。在一實作中，程式邏輯 可運作以從另一程式處被計劃性地呼叫，像是對一在 術。 邏輯 段的 第二 對輸 更多 的邏 易的 12， 順序 若該 置在 邏輯 於建 交易 迴圈 的使 序迴 邏輯 憶體 某些 能用 .504 程式 22 200903339 程序使用單〜呼叫。
第1 4圖’兹說明牽涉到將一原始循序迴圈轉 圈的呵陏階畏的一實作。在一形式中，第】4 是至^部分地實現在計算裝置100之作業邏 開始於起始點550並藉由採用該循序迴圈之 生一跟隨一預先決定承諾順序處理的分離交 —個別工作項目）的方式，來將一原始循序迴 行迴圈’藉此遵守一與該原始循序迴圈之原 承諸順序（階段5 5 2)。在另一實作中，在每 交易會被認為代價太高的情況下，迭代的連 續條碼（stripe)(例如相鄰條碼）可被合併群組成一交易（階 段552)。該系統產生該平行迴圈而無須執行該原始循序迴 圈的編譯器分析（階段5 5 4)。接著則執行該平行迴圈’其 中至少某些的分離交易被分派到不同執行緒，故他們能以 平行方式執行（階段5 5 6)。該處理在結束點5 5 8處終止。
邏輯504中之 現在來到 換成一平行迴 圖之處理程序 輯中。該程序 各迭代以及產 易（例如含括 圈轉換成一平 始執行相符的 一迭代建立一 第1 5圖說明牵涉到使用一預先決定承諾順序處理以 確保在該平行迴圈中之交易能按一適當順序被承諾的該等 P白&的一實作。在—形式中，第1 5圖之處理程序是至少部 分地實現在計算裝置1〇〇之作業邏輯中。該程序開始於起 始點570並將一原始循序迴圈轉換成一跟隨一預先決定承 諾順序處理的平行迴圈（階段572)。該系統用一承諾順序 數目來分派在該平行迴圈中之各交易（或使用另一合適方 式來追蹤一承諾該等交易之順序）（階段574)。當該平行迴 圏正在執行時’該系統使用該預先決定承諾順序來確保個 23 200903339 別交易各者只在該平行迴圈之進行中迭代已經成功地完成 之後才可完成（例如讓該交易等待直到其承諾順序顯示它 可承諾）（階段 5 7 6)。該處理在結束點5 7 8處終止。 第1 6圖說明牽涉到使用一承諾仲裁器來偵測並處置 在執行該平行迴圈的同時所發生之衝突的該等階段之一實 作。在一形式中，第1 6圖之處理程序是至少部分地實現在 計算裝置1 〇 〇之作業邏輯中。該程序開始於起始點6 0 0並 將一原始循序迴圈轉換成一使用一預先決定承諾順序處理 以確保適當排序的平行迴圈（階段 602)。該系統執行該平 行迴圈（階段 604)。然後該系統偵測該平行迴圈含有多於 一的分離交易（例如迴圈迭代），該等分離交易將會修改該 相同之資料元件（例如因為缺乏執行緒安全性、因為排序 需求等等）（階段606)。一旦前導子交易已經完成，則使用 一承諾仲裁器來偵測並處置在執行該平行迴圈的同時所發 生之衝突，像是藉由偵測失序（out-of-order)執行以及排列 後續者交易之重新執行的方式（階段6 0 8)。該處理在結束 點6 1 0處終止。 第1 7圖說明牵涉到使用一承諾仲裁器來偵測並處置 在執行該平行迴圈的同時所發生之未處置異常（exception) 的該等階段之一實作。在一形式中，第17圖之處理程序是 至少部分地實現在計算裝置1 00之作業邏輯中。該程序開 始於起始點630並將一原始循序迴圈轉換成一平行迴圈， 該平行迴圈使用交易以保留一原始輸入對輸出之對映並增 進安全性（階段 632)。該系統執行該平行迴圈（階段 24 200903339 6 3 4)，然後在該平行迴圈正在執行的同時，偵測到一未處 置異常，其發生在一特定交易内（階段 63 6)。由該特定交 易所造成之狀態修改以及該特定交易之任何前導子交易被 承諾（階段6 3 8)。在推論上能由任何後續者交易對該特定 交易所造成的狀態修改，能藉由回捲其交易的方式而放棄 (階段 64 0)。該處理在結束點642處終止。
第1 8 A-1 8 B圖說明一種假設性的來源程式碼，其用於 從一原始循序迴圈到一平行迴圈的示範性轉換。同時第 18A圖顯示一原始循序迴圈650其含有一 for...each迴圈 6 5 2，吾人將了解到其他形式的迴圈架構亦可被使用。對於 在該迴圈中之各個迭代，執行一或更多的陳述式 (statement)654。第1 8B圖顯示在使用了此處討論之某些技 術來將循序迴圈轉換成一平行迴圈660之後，該循序迴圈 看起來會變得如何的一假設性範例。在所示範例中，係藉 由產生一用於該原始循序迴圈664之各迭代的分離交易， 來建立該平行迴圈。在另一實作中，在每一迭代建立一交 易會被認為代價太高的情況下，迭代的連續條碼（例如相 鄰條瑪）可被合併群組成一交易。各個分離交易則建立一新 的工作項目，以用於執行曾如陳述式6 6 7般被含括在該原 始迴圈中之該工作。一分離類別662可被用來宣告該等工 作項目迭代。該等分離交易則被分派至不同執行緒，故他 們可按平行方式來執行。 第19圖說明牵涉到將一閉路端（closed ended)之循序 迴圈轉換成一平行迴圈的該等階段的一實作。在一形式 25 200903339
中，第1 9圖之處理程序是至少部分地實現在計算裝置1 0 0 之作業邏輯中。該程序開始於起始點6 7 0並提供一交易記 憶體系統（階段 6 7 2)。該系統分析程式碼之第一區段（其含 有一原始循序迴圈），以決定該原始循序迴圈將執行的迭代 固定數目（例如 透過擷取一用於決定迴圈終止的常數 值）（階段674)。含有該原始循序迴圈之該程式碼第一區段 係被轉換成含有一平行迴圈之程式碼之第二區段，該平行 迴圈可產生最多可達到迭代固定數目的交易（階段676)。 該系統使用該交易記憶體系統來執行該程式碼之第二區 段，其中至少某些交易被分派到不同執行緒，故他們能以 平行方式執行（階段6 7 8)。該系統按一適當順序使用一預 先決定承諾順序處理來承諾該等交易（例如其中各交易使 用一如該承法循序數目般的個別感應變數（induction variable)計數器）（階段 680)。該處理在結束點682處終止。 在一實作中，在第19圖中所描述之該轉換處理是僅用 於該感應變數從未被寫入到該迴圈主體本身的迴圈。換言 之，一迴圈可藉由將該感應變數寫入到該迴圈主體内的方 式而被取消資格，或是藉由採用一感應變數之位址並對其 採取可導致一寫入的動作（傳遞到一函式、將其別名化等 等）。 第20圖說明牵涉到使用一推測管線將一開路端（open e n d e d)之循序迴圈轉換成一平行迴圈的該等階段的一實 作。在一形式中，第2 0圖之處理程序是至少部分地實現在 計算裝置1 〇 0之作業邏輯中。該程序開始於起始點7 0 0並 26 200903339
提供一交易記憶體系統（階段 7 0 2)。該系統將程式碼之第 一區段（其含有一開路端循序迴圈）轉換成程式碼之第二區 段（其含有一可運作以產生一分離交易的平行迴圈，該分離 交易含有一用於推測管線之各迭代的個別工作項目）（例如 至少某些交易以平行方式執行）（階段7 04)。該程式碼之第 二區段無須執行該開路端循序迴圈之編譯器分析即可被產 生（階段7 0 6 )。該系統使用該交易記憶體系統來執行程式 碼之第二區段，其中至少某些交易被分派到不同執行緒， 故他們能以平行方式執行（階段 7 0 8)。一原始輸入對輸出 對映係藉由承諾在一預先決定承諾順序中之該等交易的方 式而被保留（例如與該開路端循序迴圈之一執行順序相 符）（階段 7 1 0)。該處理在結束點7 1 2處終止。 第2 1圖說明牽涉到執行一平行迴圈（其曾從一開路端 循序迴圈處所產生）的該等階段的一實作。在一形式中，第 2 1圖之處理程序是至少部分地實現在計算裝置1 0 0之作業 邏輯中。該程序開始於起始點7 3 0並產生一估測迭代數目 之推測管線，以執行一平行迴圈，其係從一開路端循序迴 圈處所產生（例如 while迴圈、do while迴圈、for迴圈等 等）（階段73 2)。在一實作中，該系統採用該推測管線之各 迭代並產生一含有一個別工作項目之分離交易（階段 7 3 4)。在另一實作中，該系統採用迭代的連續條碼（例如相 鄰條碼）並將其合併群組成一交易，像是在每一迭代建立一 交易會被認為代價太高的情況下（階段 7 3 4)。該系統將該 等分離交易分派至不同執行緒，故他們可按平行方式來執 27 200903339 行（階段 7 3 5)。該系統估測個別工作項目各者的終端狀態 (階段 7 3 6)。當該等個別工作項目之特定一者決定要終止 該平行迴圈的時間已經來到，則該等前導子被承諾並放棄 該等後續者（階段 738)。該處理在結束點740處終止。
第2 2圖說明牽涉到確保在該平行迴圈（其曾從一開路 端循序迴圈處所產生）中之各工作項目能按一適當順序承 諾的該等階段之一實作。在一形式中，第2 2圖之處理程序 是至少部分地實現在計算裝置100之作業邏輯中。該程序 開始於起始點7 6 0並當在一個別交易中之個別工作項目各 者執行時，擷取一目前迭代值（階段7 6 2)。在一實作中， 係藉由執行一將數值微量增加（其可對個別工作項目各者 存取）的方式來擷取該目前迭代值（階段 762)。該系統使用 個別項目各者的目前迭代值，以作為在一於先決定之承諾 順序處理中之一承諾循序數目（階段 764)。該系統達成一 與該開路端循序迴圈之原始執行相符的承諾順序（階段 7 66)。該處理在結束點768處終止。 第23圖說明牵涉到計算一推測管線已決定有多少迭 代含括在該平行迴圈内之該等階段的一實作。在一形式 中，第23圖之處理程序是至少部分地實現在計算裝置100 之作業邏輯中。該程序開始於起始點7 9 0並且該系統產生 該推測管線之一初始值，其係至少部分基於在一執行該平 行迴圈之電腦上的可用處理器數目（階段 792)。在一實作 中，該推測管線之初始值係依據處理器的數目所計算，該 等處理器數目係依花在執行CPU限制（CPU-bound)工作上 28 200903339 之工作量的時間比例來劃分（階段 792)。亦可使用其他眾 多的計算方式。該初始值被用來決定有多少平行迴圈之迭 代能用來建立該平行迴圈之特定執行（階段 7 9 4)。該系統 可使用適合的統計數值來調整用於該平行迴圈之較晚執行 的推測管線（例如使用歷史紀錄以較佳地決定該迴圈之期 望持續時間，以當一工作項目阻斷時適當地調整等等）（階 段796)。該處理在結束點798處終止。
第2 4 A到2 4 B圖說明一種假設性的來源程式碼，其用 於從一原始開路端循序迴圈到一平行迴圈的示範性轉換。 該術語「開路端循序迴圈」係意指包括了其迭代數目為未 知的循序迴圈。如第24A圖所示，茲顯示一原始開路端循 序迴圈810。該迴圈為一 while迴圈，其當該狀態為真時 執行若干陳述式（例如在所示範例中 w h i 1 e P = t r u e)。第 24B圖說明該原始開路端循序迴圈如何被轉換成一平行迴 圈8 2 0。如第2 4 B圖的假設性程式碼所示，對於該推測管 線之各迭代而言，能產生一以平行方式運行的工作項目。 在一實作中，一標準工作竊用（stealing)佇列可針對此來使 用。一被稱為currentlteration的共享變數係可對各工作項 目存取。當各工作項目執行時，其對currentlteration執行 微小增量，像是藉由標準的比較並交換（comp are-and-swap) 硬體指令或另一機制，來提取其自身的迭代值。此確保了 任何一個迭代僅由一單一工作者來處置，且交易開始執行 該迴圈之多個迭代其中之一的順序可被決定。然後，此變 成了該交易之承諾循序數目並確保該迭代在按正確順序的 29 200903339 前導子及後續者間為可序列化（serializable)。當該迴圈架 構指定時，各工作項目估測P或是不論終止狀態式在該工 作之前或之後為可應用（例如假設在第 2 4 B途中所示的 “while”之前，但是在do-while“之後”）。當由該等工作者其 中之一完成真實化時，即是終止的時間到了 ，所有前導子 必須承諾，且然後所有後續者必須被放棄。
雖然在此所述的範例是在討論關於使用各種科技及技 術來強制執行承諾排序，吾人應了解到一交易或許根本不 具有一承諾仲裁器。在交易根本不具有一承諾仲裁器的情 況下，會發生一普通的未排序承諾。 雖然該標的已經以特定於結構化特徵及/或方法性步 驟的語言來描述，其應瞭解到在後附申請專利範圍中的標 的並不需要限制於上述之特定特徵或步驟。而是上述的特 定特徵與步驟係以實施該等申請專利範圍之範例型式來揭 示。所有落於在此描述及/或藉由以下申請專利範圍描述之 實施的精神内之均等、改變及修正係需要受保護。 例如，熟習電腦軟體技術人士將會確認到，本文中討 論之實例内所描述的客戶端及/或伺服器配置、使用者介面 螢幕内容、及/或資料布局，可在一或多數電腦上按不同方 式組織，以含括比實例中描述之較少或額外選項或特徵。 【圖式簡單說明】 第1圖係一實作之電腦系統的示意圖。 第2圖係一運作在第1圖之電腦系統上之實作的交易 30 200903339 記憶體應用程式的不意圖。 第3圖係一用於第1圖系統之一實作的高階處理流程 圖。 第4圖係一用於第1圖系統之一實作的處理流程圖， 其說明牽涉到使用一承諾仲裁器以強制執行一預先決定承 諾順序的該等階段。
第5圖係一用於第1圖系統之一實作的處理流程圖， 其說明牽涉到使用一承諾仲裁器以強制執行複數個交易之 整體排序的該等階段。 第6圖係一用於第1圖系統之一實作的處理流程圖， 其說明牵涉到使用一承諾仲裁器以強制執行複數個交易之 部分排序的該等階段。 第7圖係一用於第1圖系統之一實作的處理流程圖， 其說明牽涉到提供一負責管理衝突（其係使用該預先決定 承諾順序資訊）之競爭管理處理的該等階段。 第8圖係一用於第1圖系統之一實作的處理流程圖， 其說明牵涉到提供一負責管理巢狀交易之衝突（其係使用 該預先決定承諾順序資訊）之競爭管理處理的該等階段的 一實作。 第9圖係一邏輯圖，其說明一具有頂層上代（其具有一 共同上代）的示範性上代樹。 第10圖係一邏輯圖，其說明一具有頂層上代（其不具 有一共同上代）的示範性上代樹。 第11圖係一用於第1圖系統之一實作的處理流程圖， 31 200903339 其說明牽涉到藉由使用一在一交易記憶體系統中之承諾仲 裁器來減少工作浪費量的該等階段。 第1 2圖係一用於第1圖系統之一實作的處理流程圖， 其說明牽涉到分析在一競爭管理處理中之一整體上代鍊以 決定適當衝突解決方案的該等階段之一實作。 第1 3圖係一運作在第1圖之電腦系統上之實作的交易 記憶體應用程式的示意圖。
第1 4圖係一用於第1圖系統之一實作的處理流程圖， 其說明牽涉到將一原始循序迴圈轉換成一平行迴圈的該等 階段。 第1 5圖係一用於第1圖系統之一實作的處理流程圖， 其說明牽涉到使用一預先決定承諾順序處理以確保在該平 行迴圈中之交易能按一適當順序被承諾的該等階段。 第1 6圖係一用於第1圖系統之一實作的處理流程圖， 其說明牽涉到使用一承諾仲裁器來偵測並處置在執行該平 行迴圈的同時所發生之衝突的該等階段。 第1 7圖係一用於第1圖系統之一實作的處理流程圖， 其說明牵涉到使用一承諾仲裁器來偵測並處置在執行該平 行迴圈的同時所發生之未處置異常（exception)的該等階 段。 第1 8 A -1 8 B圖說明一種假設性的來源程式碼，其用於 從一原始循序迴圈到一平行迴圈的示範性轉換。 第1 9圖係一用於第1圖系統之一實作的處理流程圖， 其說明牵涉到將一閉路端之循序迴圈轉換成一平行迴圈的 32 200903339 該等階段。 第2 0圖係一用於第1圖系統之一實作的處理流程圖， 其說明牽涉到使用一推測管線將一開路端之循序迴圈轉換 成一平行迴圈的該等階段 第21圖係一用於第1圖系統之一實作的處理流程圖， 其說明牵涉到執行一平行迴圈（其曾從一開路端循序迴圈 處所產生）的該等階段。
i 第2 2圖係一用於第1圖系統之一實作的處理流程圖， 其說明牵涉到確保在該平行迴圈（其曾從一開路端循序迴 圈處所產生）中之各工作項目能按一適當順序承諾的該等 階段。 第2 3圖係一用於第1圖系統之一實作的處理流程圖， 其說明牽涉到計算一推測管線已決定有多少迭代含括在該 平行迴圈内之該等階段。 第2 4 A - 2 4 Β圖說明一種假設性的來源程式碼，其用於 從一原始開路端循序迴圈到一平行迴圈的示範性轉換。 【主要元件符號說明】 100 計 算 裝 置 1 02 處 理 單 元 104 系 統 記 憶 體 106 基 本 組 態 108 可 移 除 式 儲 存 裝 置 110 不 可 移 除式儲存裝置 111 m 出 裝 置 112 輸 入 裝 置 114 通 訊 連 接 115 其 他 電 腦/應用程式 200 交 易 記 憶 體 應 用 程式 33

Claims (1)

  1. 200903339 十、申請專利範圍： 1. 一種將一閉路端循序迴圈轉換成一平行迴圈的方法，其 至少包含以下步驟： 提供一交易記憶體系統； 分析程式碼之一第一區段（其含有一原始循序迴圈）， 以決定該原始循序迴圈所能執行的一迭代固定數目；
    將程式碼之該第一區段（其含有該原始循序迴圈）轉換 成程式碼之一第二區段（其含有一平行迴圈），該平行迴圈 係可運作以產生數量多達該迭代固定數目之複數個交易， 該等交易讓至少一部份的平行迴圈能以平行方式執行；以 及 使用該交易記憶體系統來執行程式碼之該第二區段， 其中至少某些的複數個交易係在不同執行緒上執行。 2.如申請專利範圍第1項所述之方法，其中該迭代固定數 目係藉由擷取一常數值的方式來決定，其中該原始循序迴 圈被拿來與該常數值比較以決定迴圈終止。 3.如申請專利範圍第1項所述之方法，其中該等交易各者 使用一個別感應變數計數器以當作一承諾循序數目，該承 諾循序數目係由一預先決定承諾順序處理所使用，以確保 該等交易各者能按一適當順序所承諾。 34 200903339 4. 一種具有電腦可執行指令之電腦可讀取媒體，其用於使 一電腦能執行如申請專利範圍第1項所述方法之該等步 驟。 5. —種具有電腦可執行指令之電腦可讀取媒體，其用於使 一電腦能執行以下步驟： 提供一交易記憶體系統；
    分析程式碼之一第一區段（其含有一原始循序迴圈）， 以決定該原始循序迴圈所能執行的一迭代固定數目； 將程式碼之該第一區段（其含有該原始循序迴圈）轉換 成程式碼之一第二區段（其含有一平行迴圈），該平行迴圈 係可運作以產生數量多達該迭代固定數目之複數個交易， 該等交易讓至少一部份的平行迴圈能以平行方式執行；以 及 使用該交易記憶體系統來執行程式碼之該第二區段， 其中至少某些的複數個交易係在不同執行緒上執行。 6.如申請專利範圍第5項所述之電腦可讀取媒體，其中產 生了程式碼之該第二區段，使得至少某些的該等交易能以 平行方式執行。 7 ·如申請專利範圍第5項所述之電腦可讀取媒體，其中產 生了程式碼之該第二區段而無須執行該開路端循序迴圈的 35 200903339 一編譯器分析。 8.如申請專利範圍第5項所述之電腦可讀取媒體，其中一 原始輸入對輸出對映係藉由按一預先決定承諾順序來承諾 該等交易的方式來保留。 9 ·如申請專利範圍第8項所述之電腦可讀取媒體，其中該 預先決定承諾順序係與該開路端循序迴圈之一執行順序相 符。 10. —種用於執行一平行迴圈（其曾從一開路端循序迴圈 中所產生）的方法，該方法至少包含以下步驟： 產生一推測管線，其估測一迭代數目以在一平行迴圈 中執行，該平行迴圈係從一開路端循序迴圈中所產生； 採用該推測管線之各迭代並產生一含有一個別工作項 目之分離交易； 在不同執行緒上執行至少某些的該等分離交易； 針對個別工作項目各者評估一終端狀態；以及 當該等個別工作項目之特定一者決定要終止該平行迴 圈的時間已經來到，則承諾該等前導子並放棄該等個別工 作項目之特定一者的該等後續者。 1 1 _如申請專利範圍第1 0項所述之方法，其中當個別工作 36 200903339 項目各者執行時，擷取一目前迭代值。 12.如申請專利範圍第11項所述之方法，其中個別工作項 目各者之目前迭代值被當作一在一預先決定承諾順序處理 之承諾循序數目來使用。 1 3 .如申請專利範圍第1 1項所述之方法，其中該目前迭代 值係藉由執行將數值微量增加（其可對個別工作項目各者 存取）的方式來擷取該目前迭代值。 1 4.如申請專利範圍第1 0項所述之方法，其中茲達成一承 諾順序，其與該開路端循序迴圈之一原始執行相符。 1 5 ·如申請專利範圍第1 0項所述之方法，其中該開路端循 序迴圈為一 while迴圈。 1 6.如申請專利範圍第1 0項所述之方法，其中該開路端循 序迴圈為一 do while迴圈。 1 7.如申請專利範圍第1 0項所述之方法，其中該開路端循 序迴圈為一 for迴圈。 1 8.如申請專利範圍第1 0項所述之方法，其中該推測管線 37 200903339 之一初始值係至少部分地基於在一執行該平行迴圈之電腦 上的可用處理器數目而計算得出。 1 9.如申請專利範圍第1 0項所述之方法，其中適合的統計 數值被用來調整用於該平行迴圈之較晚執行的推測管線。
    20. —種具有電腦可執行指令之電腦可讀取媒體，其用於 使一電腦能執行如申請專利範圍第1 0項所述方法之該等 步驟。 C, 38
TW097118420A 2007-06-04 2008-05-19 使用交易以平行化循序框架之方法及電腦可讀取媒體 TWI451340B (zh)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US11/810,111 US8024714B2 (en) 2006-11-17 2007-06-04 Parallelizing sequential frameworks using transactions

Publications (2)

Publication Number Publication Date
TW200903339A true TW200903339A (en) 2009-01-16
TWI451340B TWI451340B (zh) 2014-09-01

Family

ID=40107429

Family Applications (1)

Application Number Title Priority Date Filing Date
TW097118420A TWI451340B (zh) 2007-06-04 2008-05-19 使用交易以平行化循序框架之方法及電腦可讀取媒體

Country Status (7)

Country Link
US (2) US8024714B2 (zh)
EP (1) EP2171592B1 (zh)
JP (2) JP2010529559A (zh)
CN (1) CN101681292B (zh)
BR (1) BRPI0811470A2 (zh)
TW (1) TWI451340B (zh)
WO (1) WO2008151046A1 (zh)

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8010550B2 (en) * 2006-11-17 2011-08-30 Microsoft Corporation Parallelizing sequential frameworks using transactions
US8621468B2 (en) * 2007-04-26 2013-12-31 Microsoft Corporation Multi core optimizations on a binary using static and run time analysis
EP2202638A4 (en) * 2007-09-21 2011-12-14 Fujitsu Ltd TRANSLATION FACILITY, TRANSLATION PROCEDURE AND TRANSLATION PROGRAM AND PROCESSOR CONTROL SYSTEM AND PROCESSOR
US8739141B2 (en) * 2008-05-19 2014-05-27 Oracle America, Inc. Parallelizing non-countable loops with hardware transactional memory
JP4612710B2 (ja) * 2008-06-02 2011-01-12 株式会社日立製作所 トランザクション並行制御方法、データベース管理システム、およびプログラム
US8667476B1 (en) * 2009-01-20 2014-03-04 Adaptmicrosys LLC Instruction grouping and ungrouping apparatus and method for an adaptive microprocessor system
US8266604B2 (en) * 2009-01-26 2012-09-11 Microsoft Corporation Transactional memory compatibility management
US20110178984A1 (en) * 2010-01-18 2011-07-21 Microsoft Corporation Replication protocol for database systems
US8825601B2 (en) * 2010-02-01 2014-09-02 Microsoft Corporation Logical data backup and rollback using incremental capture in a distributed database
CN104572506B (zh) * 2013-10-18 2019-03-26 阿里巴巴集团控股有限公司 一种并发访问内存的方法及装置
US9454313B2 (en) 2014-06-10 2016-09-27 Arm Limited Dynamic selection of memory management algorithm
CN104317850B (zh) * 2014-10-14 2017-11-14 北京国双科技有限公司 数据处理方法和装置
JP6645348B2 (ja) 2016-05-06 2020-02-14 富士通株式会社 情報処理装置、情報処理プログラム、及び情報処理方法
US11521242B2 (en) * 2016-08-31 2022-12-06 Meta Platforms, Inc. Asynchronous execution of tasks and ordering of task execution
EP3594804B1 (en) * 2018-07-09 2021-11-03 ARM Limited Transactional compare-and-discard instruction

Family Cites Families (59)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB8306813D0 (en) 1983-03-11 1983-04-20 Bonas Machine Co Heald control apparatus
US4884228A (en) * 1986-10-14 1989-11-28 Tektronix, Inc. Flexible instrument control system
JPH01108638A (ja) * 1987-10-21 1989-04-25 Hitachi Ltd 並列化コンパイル方式
JPH0475139A (ja) * 1990-07-18 1992-03-10 Toshiba Corp ループ並列化装置
DE4216871C2 (de) 1991-05-21 2001-09-06 Digital Equipment Corp Ausführungsordnen zum Sicherstellen der Serialisierbarkeit verteilter Transaktionen
US5701480A (en) * 1991-10-17 1997-12-23 Digital Equipment Corporation Distributed multi-version commitment ordering protocols for guaranteeing serializability during transaction processing
JPH05127904A (ja) * 1991-11-05 1993-05-25 Matsushita Electric Ind Co Ltd 情報処理装置及びコード生成装置
JPH05173988A (ja) * 1991-12-26 1993-07-13 Toshiba Corp 分散処理方式および該分散処理に適用されるトランザクション処理方式
US5241675A (en) * 1992-04-09 1993-08-31 Bell Communications Research, Inc. Method for enforcing the serialization of global multidatabase transactions through committing only on consistent subtransaction serialization by the local database managers
US5335343A (en) * 1992-07-06 1994-08-02 Digital Equipment Corporation Distributed transaction processing using two-phase commit protocol with presumed-commit without log force
US6704861B1 (en) * 1993-06-17 2004-03-09 Hewlett-Packard Development Company, L.P. Mechanism for executing computer instructions in parallel
JPH0784851A (ja) * 1993-09-13 1995-03-31 Toshiba Corp 共有データ管理方法
US5799179A (en) 1995-01-24 1998-08-25 International Business Machines Corporation Handling of exceptions in speculative instructions
JP3434405B2 (ja) * 1996-03-19 2003-08-11 富士通株式会社 通信制御装置及び通信制御方法並びに中間通信制御ユニット
US5920724A (en) * 1996-03-28 1999-07-06 Intel Corporation Software pipelining a hyperblock loop
JPH1049420A (ja) 1996-08-02 1998-02-20 Fuji Xerox Co Ltd データベース管理方法
US5898865A (en) * 1997-06-12 1999-04-27 Advanced Micro Devices, Inc. Apparatus and method for predicting an end of loop for string instructions
CA2209549C (en) * 1997-07-02 2000-05-02 Ibm Canada Limited-Ibm Canada Limitee Method and apparatus for loading data into a database in a multiprocessor environment
JP3052908B2 (ja) * 1997-09-04 2000-06-19 日本電気株式会社 トランザクションプログラム並列実行方法およびトランザクションプログラム並列実行方式
US7065750B2 (en) * 1999-02-17 2006-06-20 Elbrus International Method and apparatus for preserving precise exceptions in binary translated code
AU6784600A (en) 1999-08-17 2001-03-13 Progress Software, Inc. Concurrent commit lock
US6438747B1 (en) * 1999-08-20 2002-08-20 Hewlett-Packard Company Programmatic iteration scheduling for parallel processors
US6507947B1 (en) * 1999-08-20 2003-01-14 Hewlett-Packard Company Programmatic synthesis of processor element arrays
US6374403B1 (en) * 1999-08-20 2002-04-16 Hewlett-Packard Company Programmatic method for reducing cost of control in parallel processes
JP4237354B2 (ja) * 1999-09-29 2009-03-11 株式会社東芝 トランザクション処理方法及びトランザクション処理システム
US6745160B1 (en) * 1999-10-08 2004-06-01 Nec Corporation Verification of scheduling in the presence of loops using uninterpreted symbolic simulation
US6557048B1 (en) * 1999-11-01 2003-04-29 Advanced Micro Devices, Inc. Computer system implementing a system and method for ordering input/output (IO) memory operations within a coherent portion thereof
US6574725B1 (en) * 1999-11-01 2003-06-03 Advanced Micro Devices, Inc. Method and mechanism for speculatively executing threads of instructions
US20040236659A1 (en) * 1999-12-01 2004-11-25 Cazalet Edward G. Method and apparatus for an engine system supporting transactions, schedules and settlements involving fungible, ephemeral commodities including electrical power
US6918053B1 (en) * 2000-04-28 2005-07-12 Microsoft Corporation Compensation framework for long running transactions
US6708331B1 (en) * 2000-05-03 2004-03-16 Leon Schwartz Method for automatic parallelization of software
US6615403B1 (en) * 2000-06-30 2003-09-02 Intel Corporation Compare speculation in software-pipelined loops
EP1197876A3 (en) 2000-10-13 2003-04-16 Miosoft Corporation Persistent data storage techniques
US7111023B2 (en) 2001-05-24 2006-09-19 Oracle International Corporation Synchronous change data capture in a relational database
US7069556B2 (en) * 2001-09-27 2006-06-27 Intel Corporation Method and apparatus for implementing a parallel construct comprised of a single task
GB0130399D0 (en) * 2001-12-19 2002-02-06 Ibm Message ordering in a messaging system
US6754737B2 (en) * 2001-12-24 2004-06-22 Hewlett-Packard Development Company, L.P. Method and apparatus to allow dynamic variation of ordering enforcement between transactions in a strongly ordered computer interconnect
KR100450400B1 (ko) * 2001-12-26 2004-09-30 한국전자통신연구원 안전 기억 장치가 없는 환경을 위한 이중화 구조의 주 메모리 상주 데이터베이스 관리시스템 및 그 데이터 일치성 제어방법
US6785779B2 (en) * 2002-01-09 2004-08-31 International Business Machines Company Multi-level classification method for transaction address conflicts for ensuring efficient ordering in a two-level snoopy cache architecture
US7328316B2 (en) * 2002-07-16 2008-02-05 Sun Microsystems, Inc. Software transactional memory for dynamically sizable shared data structures
US7103612B2 (en) 2002-08-01 2006-09-05 Oracle International Corporation Instantiation of objects for information-sharing relationships
US7076508B2 (en) * 2002-08-12 2006-07-11 International Business Machines Corporation Method, system, and program for merging log entries from multiple recovery log files
US7146366B2 (en) * 2002-09-13 2006-12-05 Netezza Corporation Distributed concurrency control using serialization ordering
US6898685B2 (en) * 2003-03-25 2005-05-24 Emc Corporation Ordering data writes from a local storage device to a remote storage device
US7185323B2 (en) * 2003-05-16 2007-02-27 Sun Microsystems, Inc. Using value speculation to break constraining dependencies in iterative control flow structures
KR100507782B1 (ko) 2003-12-04 2005-08-17 한국전자통신연구원 데이터베이스 관리시스템 및 그 시스템에서 시스템테이블에 대한 동시성 제어 방법
US20050210185A1 (en) * 2004-03-18 2005-09-22 Kirsten Renick System and method for organizing data transfers with memory hub memory modules
US7386842B2 (en) * 2004-06-07 2008-06-10 International Business Machines Corporation Efficient data reorganization to satisfy data alignment constraints
US7266571B2 (en) * 2004-07-27 2007-09-04 International Business Machines Corporation Method and system for scheduling a partial ordered transactions for event correlation
US7921407B2 (en) * 2004-08-10 2011-04-05 Oracle America, Inc. System and method for supporting multiple alternative methods for executing transactions
US7376675B2 (en) * 2005-02-18 2008-05-20 International Business Machines Corporation Simulating multi-user activity while maintaining original linear request order for asynchronous transactional events
US7627864B2 (en) * 2005-06-27 2009-12-01 Intel Corporation Mechanism to optimize speculative parallel threading
US7536517B2 (en) 2005-07-29 2009-05-19 Microsoft Corporation Direct-update software transactional memory
US20070113056A1 (en) * 2005-11-15 2007-05-17 Dale Jason N Apparatus and method for using multiple thread contexts to improve single thread performance
KR100806274B1 (ko) * 2005-12-06 2008-02-22 한국전자통신연구원 멀티 쓰레디드 프로세서 기반의 병렬 시스템을 위한 적응형실행 방법
US7926046B2 (en) * 2005-12-13 2011-04-12 Soorgoli Ashok Halambi Compiler method for extracting and accelerator template program
US7720891B2 (en) * 2006-02-14 2010-05-18 Oracle America, Inc. Synchronized objects for software transactional memory
US8010550B2 (en) * 2006-11-17 2011-08-30 Microsoft Corporation Parallelizing sequential frameworks using transactions
US7937695B2 (en) * 2007-04-27 2011-05-03 International Business Machines Corporation Reducing number of exception checks

Also Published As

Publication number Publication date
WO2008151046A1 (en) 2008-12-11
CN101681292B (zh) 2012-10-10
US8402447B2 (en) 2013-03-19
BRPI0811470A2 (pt) 2014-11-04
JP2014146355A (ja) 2014-08-14
US20110283091A1 (en) 2011-11-17
CN101681292A (zh) 2010-03-24
TWI451340B (zh) 2014-09-01
JP5813165B2 (ja) 2015-11-17
JP2010529559A (ja) 2010-08-26
US8024714B2 (en) 2011-09-20
EP2171592B1 (en) 2019-04-10
EP2171592A1 (en) 2010-04-07
US20080120298A1 (en) 2008-05-22
EP2171592A4 (en) 2012-03-21

Similar Documents

Publication Publication Date Title
TWI442233B (zh) 使用交易以平行化循序框架之方法及用於記錄相關指令之電腦儲存媒體
TWI451340B (zh) 使用交易以平行化循序框架之方法及電腦可讀取媒體
KR101443930B1 (ko) Ｓｔｍ 시스템에서 트랜잭션들에 순서화를 적용하는 방법, 순서화에 의한 경쟁 관리를 제공하는 방법 및 컴퓨터 판독가능 매체
US7860847B2 (en) Exception ordering in contention management to support speculative sequential semantics
US10331666B1 (en) Apparatus and method for parallel processing of a query
US9009734B2 (en) Application level speculative processing
US8739186B2 (en) Application level speculative processing
WO2017148508A1 (en) Multi-phase high performance business process management engine