分配共享堆棧的部分的系統和方法

2023-07-19 06:23:51 1

專利名稱：分配共享堆棧的部分的系統和方法
分配共享堆棧的部分的系統和方法技術領域
本發明大體涉及數據處理，且更特定來說涉及存儲器堆棧操作。
背景技術：
技術的進步已產生可用於執行各種任務的更強大的計算裝置。計算裝置通常包含 至少一個處理器。為改進計算裝置內的指令的處理，處理器有時使用分支預測來預期程序 代碼內的分支形成。微處理器可使用返回地址堆棧(RAS)來預測程序執行期間遇到的呼叫 /返回類型分支的返回地址。RAS可為堆棧(後進先出(LIFO)數據結構)的特殊實施方案。 呼叫指令可致使將返回地址推送到RAS上。返回指令可致使從堆棧彈出位於RAS頂部的地 址且用於預測返回地址。當分支預測成功時，從RAS頂部彈出的地址可用於重定向處理器 的指令提取單元。當分支預測不成功時，可計算正確的返回地址以便正確地重定向指令提 取單元。
多線程處理器的每一線程可使用其自身的專門RAS，且每一 RAS可具有固定大小。 每一線程可依據正由每一線程執行的指令流而使用其固定大小RAS的不同數目的條目。然 而，多個返回地址堆棧的使用增加了系統的成本。發明內容
一特定實施例可允許對共享堆棧的多線程存取。對共享堆棧的存取可依據每一線 程的當前需要而動態分配給多個線程。共享堆棧的條目可由線程經由線程指針的操縱來指 派和覆寫。因為移動線程指針而非移動堆棧地址條目，所以可減少處理和功率需求。共享 堆棧可包含比常規靜態多線程返回地址堆棧少的條目，因為共享堆棧的條目可在線程之間 更有效地分布。較少堆棧條目可轉化為裸片上的較小空間需求以及增加的性能。
在一特定實施例中，揭示一種設備，其包含共享堆棧。所述設備進一步包含控制 器，所述控制器可操作以選擇性地將共享堆棧的第一部分分配給第一線程，且選擇性地將 共享堆棧的第二部分分配給第二線程。
在另一特定實施例中，一種管理由處理器的多個線程共享的堆棧的方法包含將共 享堆棧的第一部分分配給第一線程，以及將共享堆棧的第二部分分配給第二線程。
在另一特定實施例中，一種計算機可讀有形媒體存儲計算機可執行的指令。所述 指令包含可由計算機執行以將共享堆棧的第一部分分配給第一線程且將共享堆棧的第二 部分分配給第二線程的指令。
所揭示的實施例中的至少一者提供的特定優點可源自共享堆棧經配置以用於由 多個線程進行共享存取。共享堆棧可包含比每一線程存取單獨堆棧的系統常規上所需要的 數目少的總條目。較小的條目總數可產生裸片上的較小空間需求以及減小的複雜性和功率 需求。所揭示的實施例中的一者或一者以上促成的減小的堆棧大小和其它優點可進一步改 進存儲器分布和堆棧存取效率。
在檢視整個申請案後，將明白本發明的其它方面、優點和特徵，申請案包含以下部分


具體實施方式
和權利要求書。

圖1是經配置以協調對共享堆棧的多線程存取的系統的特定說明性實施例的框圖2是包含經配置以存取共享堆棧的經激活線程的系統的特定說明性實施例的框圖3是經配置以使線程能夠動態存取共享堆棧的條目的系統的特定說明性實施例的框圖4是經配置以當第二線程變為作用中且存取共享堆棧時協調對共享堆棧的多線程存取的系統的特定說明性實施例的框圖5是經配置以當第二線程獲取共享堆棧的條目且準備覆寫第一線程的條目時協調對共享堆棧的多線程存取的系統的特定說明性實施例的框圖6是經配置以當第二線程覆寫第一線程的條目時協調對共享堆棧的多線程存取的系統的特定說明性實施例的框圖7是管理由處理器的多個線程共享的堆棧的方法的特定說明性實施例的流程圖8是實現對共享堆棧的多線程存取的方法的特定說明性實施例的流程圖；以及
圖9是包含多個線程上的共享堆棧存取的可攜式裝置的框圖。
具體實施方式
本發明揭示一種系統，其包含由多線程處理器的多個線程共享 的存儲器堆棧。共享堆棧的條目可由堆棧控制器動態分配給給定線程。利用此分配，共享堆棧的每一線程的所分配部分經設定大小以實現有效堆棧利用率且考慮到公平策略。共享堆棧可包含比各自專用於不同線程的單獨堆棧將使用的數目少的堆棧條目。
參看圖1，描繪在多個線程之間共享堆棧的系統的特定實施例，且其大體表示為 100。系統100包含耦合到存儲器104的控制器102。控制器102響應於多線程處理器160。 存儲器104包含共享堆棧105。控制器102響應於來自多線程處理器160的堆棧操作請求以向多線程處理器160的個別線程分配和解除分配共享堆棧105的部分，且執行用於發出請求的線程的共享堆棧105的堆棧操作。
多線程處理器160可包含可執行一個或一個以上線程的一個或一個以上多線程處理器核心106。舉例來說，多線程處理器160可執行第一線程108 (線程O)、第二線程 110(線程I)、第三線程112(線程2)和第η線程114(線程(η_1))。多線程處理器160可向控制器102發送針對線程108-114中的一者或一者以上的堆棧操作請求。舉例來說，多線程處理器160可向控制器102發送推送請求138，其識別產生推送請求138的線程且進一步識別待推送到共享堆棧105的發出請求的線程的部分上的數據。作為另一實例，多線程處理器160可向控制器102發送彈出請求136。彈出請求136可識別多個線程108-114中的發出請求的線程，且請求最近添加到共享堆棧105的發出請求的線程的部分的數據的返回。
控制器102操作以選擇性地將共享堆棧105的部分分配給個別線程。舉例來說， 控制器102可選擇性地將共享堆棧105的第一部分116分配給第一線程108，將共享堆棧 105的第二部分118分配給第二線程110，將共享堆棧105的第三部分120分配給第三線程 112，且將共享堆棧105的第η部分122分配給第η線程114。在特定實施例中，共享堆棧 105可包含硬體堆棧。或者，共享堆棧105可實施在例如隨機存取存儲器(RAM)等其它存儲器中。
控制器102響應於服從公平策略140的線程請求而分配共享堆棧105的部分 116-122，且經由堆棧指針142維持指示經分配部分116-122的分配和使用的數據。舉例來說，公平策略140可指示在線程之間同等地、以用於每一線程的固定大小部分、以用於每一執行中線程的固定大小部分、以用於每一線程的可變大小部分、以用於每一執行中線程的可變大小部分、以相對於堆棧未中的數目的經加權平均大小部分或以某一其它方式分配共享堆棧105。堆棧指針142包含對應於第一線程108的指針162、對應於第二線程110的指針164、對應於第三線程112的指針166和對應於第η線程114的指針168。舉例來說，線程指針162-168中的每一者可包含頂部條目指針、堆棧頂部指針、堆棧底部指針、底部條目指針，以及一個或一個以上額外狀態位，如參看圖2-6所描述。控制器102使用指針162-168 來維持使用循環緩衝器分配給每一線程的單獨堆棧。
第一部分116可經分配用於對應於第一線程108的堆棧操作。第一部分116可包含可存儲第一線程108的一個或一個以上數據元素124的一個或一個以上堆棧條目(未圖示)。第二部分118可經分配用於第二線程110的堆棧操作，且可包含可存儲第二線程110 的一個或一個以上數據元素126的一個或一個以上堆棧條目。第三部分120可經分配用於對應於第三線程112的堆棧操作，且可包含可存儲第三線程112的一個或一個以上數據元素128的一個或一個以上堆棧條目。第η部分122可經分配用於對應於第η線程114的堆棧操作，且可包含可存儲第η線程114的一個或一個以上數據元素130的一個或一個以上堆棧條目。
在操作期間，多線程處理器160的一個或一個以上線程可產生堆棧操作請求，例如推送請求138。控制器102可接收推送請求138且確定發出請求的線程(例如，第一線程 108)是否在其經分配部分(例如，第一部分116)中具有足夠空間來容納數據的添加(例如，到第一線程108的數據元素124)。如果第一部分116不包含足夠空間，那麼控制器102 可根據公平策略140確定是否將額外空間動態分配給第一線程108。舉例來說， 當其它線程110-114不在使用共享堆棧105的剩餘部分時，控制器102可將額外存儲器動態分配給第一部分116以容納對應於第一線程108的額外推送請求。
或者，當多個線程110-114正主動使用共享堆棧105時，控制器102可防止向第一線程108分配多於如公平策略140所確定的共享堆棧105的公平共享份額。共享堆棧的每一部分可使用循環緩衝器來實施。當控制器102確定可滿足推送請求138時，控制器102 起始存儲器操作150，所述存儲器操作150可包含將針對推送請求138的所接收數據寫入到第一部分116內的第一線程108的數據元素124中的一者。控制器102還可更新第一線程指針162以指示當第一部分已重新設定大小時堆棧的頂部條目的改變。
控制器102還可經配置以從線程中的任一者(例如，從第一線程108)接收彈出請求136。響應於彈出請求136，控制器102經配置以起始存儲器操作150，以從第一線程108的數據元素124讀取最近添加的數據元素且響應於彈出請求136將數據134返回到多線程 處理器160。舉例來說，當共享堆棧105實施為函數返回地址堆棧(RAS)時，返回數據134 包含對應於所請求線程(例如，第一線程108)的函數返回地址。另外，控制器102可更新 第一線程指針162以指示堆棧頂部已彈出且響應於滿足彈出請求136而減少第一部分116 內的堆棧空間使用的分配。
在控制器102經由第一指令預測函數返回地址的特定實施例中，來自共享堆棧 105的誤預測函數返回地址導致隨後返回經校正的函數返回地址。舉例來說，多線程處理器 160可接收待執行的指令(例如，返回指令)的形式的彈出請求136。返回執行可花費多個 循環來完成。在返回指令的執行開始時，返回地址可從共享堆棧105彈出。此彈出的返回 地址可為用於重定向指令提取的推測性地址。隨著返回指令繼續執行(例如，通過多線程 處理器160的管線)，多線程處理器160可計算「實際」(例如，非推測性)返回地址。當返 回指令已完成執行時，可將推測性與非推測性返回地址進行比較。當返回地址不匹配(例 如，已發生分支誤預測)時，可使用「實際」返回地址來提取指令。可清除「不正確」提取的 指令。
由於控制器102實施公平策略140以響應於推送操作請求138動態分配共享堆 棧105的部分，所以共享堆棧105可由多個線程108-114使用和動態分配，使得向每一線程 108-114提供共享堆棧105的不同部分，其作為個別堆棧操作以實現共享堆棧105內的總堆 棧條目的有效利用。個別線程108-114之間共享堆棧105的部分116-122的分配和解除分 配可經由控制器102的操作和對堆棧指針142的控制來執行，使得無需在共享堆棧105內 移動數據元素124-130。而是，可在數據元素124-130周圍「移動」共享堆棧105的經分配 部分116-122。因此，共享堆棧105可被有效使用且可容納來自多個線程108-114的堆棧操 作，並可使用比針對每一線程108-114包含單獨專門堆棧的系統少的總堆棧條目。
儘管圖1中展示四個線程和四個部分，但共享堆棧105可包含供兩個或兩個以上 線程使用的兩個或兩個以上部分。並且，雖然存儲器104、控制器102和處理器160展示為 單獨組件，但應了解，此類組件中的兩者或兩者以上可集成在單一裝置上。
參看圖2，描繪說明經配置以存取共享堆棧的多個線程中的一者的執行的系統的 特定說明性實施例的框圖，且其大體表示為200。更特定來說，線程112可變為脫離復位狀 態而在作用中且可被分配得到共享堆棧105的條目222。圖2的線程108、110和112可與 圖1的線程108、110和112相同，且圖2的共享堆棧105可與圖1的共享堆棧105相同。線 程112可經由使用其指針252、254、256和258而獲取共享堆棧105的條目222的所有權。
線程112 (例如，線程2)可包含線程112可寫入到的頂部條目指針(TEP) 252。頂 部條目指針252可指向共享堆棧105內的最頂部條目。線程112還可包含堆棧頂部指針 (TSP) 254。堆棧頂部指針254可指向與線程112相關聯的共享堆棧105內的頂部或最近寫 入的條目。最近寫入的條目可包含將在堆棧彈出操作後即刻返回的數據。線程112內包含 的堆棧底部指針(BSP) 256可指向與線程112相關聯的共享堆棧105內的最老有效條目。線 程112可進一步包含底部條目指針(BEP) 258。底部條目指針258可指向線程112可寫入到 的共享堆棧105的最底部條目。線程112可進一步包含線程作用中狀態位(TASB) 260。線 程作用中狀態位260可指示線程112是否正在執行過程。如果線程112不在執行過程，那 麼可不向線程112分配共享堆棧105的條目。
線程112進一步包含纏繞堆棧位(WSB) 264。纏繞堆棧位264可指示共享堆棧105 是否響應於堆棧頂部指針254和/或堆棧底部指針256前進以指向共同條目而已纏繞。舉 例來說，纏繞堆棧位264可設定為邏輯I值以指示堆棧頂部指針254已纏繞而到達堆棧底 部指針256。在纏繞堆棧位264設定為邏輯I值的情況下，後續推送可致使堆棧底部指針 256和堆棧頂部指針254兩者遞增。推送操作可額外致使覆寫共享堆棧中的最老條目(由 堆棧底部指針256指向)。在線程的纏繞堆棧位264具有邏輯I值的同時發生從共享堆棧 105的彈出操作的情況下，纏繞堆棧位264可變換為O值。
線程112還包含空/滿位(EFB) 262。空/滿位262可經配置以指示是否使用共享 堆棧105的與線程112相關聯的條目。舉例來說，當線程112的數據存在於共享堆棧105 中時，空/滿位262可包含邏輯I值。相反，當線程112無數據存儲在共享堆棧105內時， 空/滿位262可包含邏輯O值。在空/滿位262為邏輯O值且進行推送操作的情況下，空/ 滿位262可變換為邏輯I值。在堆棧頂部指針254和堆棧底部指針256兩者指向同一條目 的同時以及纏繞堆棧位264等於邏輯O值的同時發生彈出操作的情況下，空/滿位262可 變換為邏輯O值。
一般來說，線程可被分配得到或者「擁有」其頂部條目指針及其底部條目指針所限 定的共享堆棧105的條目。線程可將數據寫入到此類「所擁有」條目。另外，線程可被認為 「利用」其堆棧頂部指針與其堆棧底部指針之間的條目。因此，共享堆棧105的條目可由特 定線程擁有，由特定線程擁有和利用，或既不由特定線程擁有也不由特定線程利用。
類似於線程112，線程110 (即，線程I)可包含頂部條目指針238和堆棧頂部指針 240。線程110可進一步包含堆棧底部指針242和底部條目指針244。線程作用中狀態位 246、空/滿位246和纏繞堆棧位250也可包含在線程110內。
線程108 (即，線程O)可包含頂部條目指針224和堆棧頂部指針226。線程108可 進一步包含堆棧底部指針228和底部條目指針230。線程作用中狀態位232、空/滿位234 和纏繞堆棧位236也可包含在線程108內。
共享堆棧105可包含存儲指令的存儲器地址的條目210、212、214、216、218、220和 222。條目210、212、214、216、218、220和222可經配置以由線程108、110和112共享。在 單一線程操作期間，線程112可變為在作用中(即，開始執行過程)。頂部條目指針252、堆 棧頂部指針254、堆棧底部指針256和底部條目指針258可設定為指向條目222，如虛線266 所指示。線程112可被認為「擁有」條目222 (例如，線程112可將數據寫入到條目222)。
空/滿位262和纏繞堆棧位264位可設定為指示空條件(例如，邏輯O值)，且線 程作用中狀態位260可設定為指示作用中條件(例如，邏輯I值)。當在線程112上執行的 過程進行呼叫時，可將地址在共享堆棧105上推送到由堆棧頂部指針254指示的條目222 中。所述地址可指示返回地址。
在線程112上執行的過程進行後續呼叫的情況下，可將另一地址推送到共享堆棧 105上進入由堆棧頂部指針254指示的條目222上方的條目220中。所述推送可致使頂部 條目指針252和堆棧頂部指針254動態遞增以指向新寫入的條目220。所述遞增可因此向 線程112分配共享堆棧105的一個或一個以上額外條目。在線程112上執行的過程指示返 回的情況下，可發生從共享堆棧105的彈出操作以檢索返回預測地址。彈出操作可致使線 程112的堆棧頂部指針254遞減，但頂部條目指針252可不遞減。
分支誤預測可由從共享堆棧105彈出的不準確返回地址引起。作為響應，存儲在堆棧105中且與誤預測線程相關聯的所有數據可被丟棄，且可重新開始線程的堆棧構建。 舉例來說，當線程112誤預測時，可通過將堆棧頂部指針254設定為等於堆棧底部指針256， 將空/滿位262的狀態設定為指示空狀態且將纏繞堆棧位264設定為指示無纏繞來起始線程112的重建。當空/滿位262等於O值時可避免彈出請求，這可節省處理功率。
圖2描繪相對於單一線程的操作。舉例來說，線程112可變為脫離復位狀態而在作用中。線程112的線程指針可初始指向共享堆棧105的單一條目(例如，條目222)。線程112可因此被認為在變為脫離復位狀態而在作用中後即刻已將其自身「錨定」在共享堆棧105的條目222處。當正由線程112執行的過程進行呼叫時，可更新線程指針(例如， 「增長」共享堆棧105的線程112的所分配部分)，同時存儲在共享堆棧105內的地址可不移位。更新線程指針而非移位共享堆棧內的地址可減小功率消耗、硬體需求和總體複雜性。
圖3說明處於與圖2中所描繪不同的處理狀態的系統200的框圖，包含作用中線程112執行過程且動態存取共享堆棧105的多個條目216、218、220和222。線程108和110 不在作用中。線程112除了條目222外還已被分配得到共享堆棧105的條目216、218和 220。條目272可未使用。
頂部條目指針252可指向條目216，如虛線270所指示。如虛線268所指示，堆棧頂部指針254可指向條目220。堆棧底部指針256和底部條目指針258兩者指向條目222， 如虛線266所指示。如此，線程112可被分配得到或「擁有」條目216、218、220和222，如線 270 (邏輯上從頂部條目指針252指出)和線266 (邏輯上從底部條目指針258指出)所限定。
圖3說明將來自共享堆棧105的條目動態分配給線程112。所述分配可通過重新指派線程指針而非移位共 享堆棧105中的條目而發生，這可促進改進的存儲器分布、改進的功率效率和減少的硬體需求。
圖4是系統200的特定說明性實施例的框圖，其中線程110 ( S卩，線程I)已變為在作用中且已被分配並將其自身錨定在共享堆棧105的未使用條目272內。條目272可位於線程112( S卩，線程2)所要求的第一條目群組210、212、214和274與第二條目群組216、 218、220 和 222 之間。
在變為在作用中(例如，有效執行過程)後，線程110可即刻將其自身錨定在共享堆棧105的條目272內。線程110可將數據元素推送到共享堆棧105中在條目272內。在特定實施例中，條目272可能先前未分配給另一線程或未由另一線程要求。在另一特定實施例中，用於錨定線程的條目可能先前已分配給另一線程。如圖4的虛線276所指示，頂部條目指針238、堆棧頂部指針240、堆棧底部指針242和底部條目指針244指向條目272。
線程110可要求另一條目且將額外數據元素推送到共享堆棧105的所要求條目上而進入條目274中。
圖4說明動態存取共享堆棧105的多個作用中線程。共享堆棧105的條目可通過修改作用中線程的線程指針而在作用中線程之間動態分配。作用中線程可根據其當前需求而被分配得到共享堆棧105的條目，這可促進有效的堆棧利用。
參看圖5，描繪系統200的特定說明性實施例，包含共享堆棧105和處於與圖4中所描繪不同的處理狀態的三個線程108、110和112。線程110和線程112在作用中且存取共享堆棧105。舉例來說，線程110已要求額外條目且正準備覆寫線程112的條目。
線程112可擁有共享堆棧105的條目，從虛線270 (邏輯上從頂部條目指針252指 出)指示的214到虛線266 (邏輯上從底部條目指針258指出)指示的條目220。
類似地，線程110可擁有共享堆棧105的條目，由條目222 (由邏輯上從頂部條目 指針238指出的線276指示)限定且纏繞在堆棧105周圍以包含條目210和212 (由邏輯 上從底部條目指針244指出的線286指示)。線程110可被認為纏繞在共享堆棧105內，因 為堆棧底部指針242在堆棧頂部指針240上方。線程110因此擁有條目210、212和222。 共享堆棧105的由線程110擁有的部分因此與線程112鄰接，且對於線程110不存在將響 應於推送而要求的自由條目。
在線程110執行到共享堆棧105上的推送且堆棧頂部指針240正指向與頂部條目 指針238相同的條目的情況下，數據可被推送到兩個位置中的一者。舉例來說，線程110可 遞增堆棧頂部指針240和頂部條目指針238兩者，藉此要求新條目和更多堆棧空間來存儲 新推送的數據，如圖6中描述。或者，線程110可纏繞在堆棧頂部指針240周圍(將頂部條 目指針238留在適當位置)且將數據寫入到由其底部條目指針244指向的條目中。選擇哪 個過程可取決於是否已要求在頂部條目指針238之後的後續條目以及線程110是否已在使 用其共享堆棧105的公平共享份額。
在未要求由頂部條目指針238指向的條目222上方的條目220的情況下，線程110 可通過更新頂部條目指針238而要求條目220。線程110可進一步將堆棧頂部指針240設 定為指向同一條目220。
在另一線程要求由頂部條目指針238指向的條目222上方的條目220且線程110 已擁有至少其堆棧105的公平共享份額的情況下，後續推送可不允許線程110要求額外堆 棧條目220。而是，堆棧頂部指針240可從頂部條目指針238向底部條目指針244纏繞。
在另一線程要求由頂部條目指針238指向的條目222上方的條目220且線程110 尚未擁有其共享堆棧105的公平共享份額的情況下，可允許推送以要求來自另一線程112 的條目220。可通過更新線程112的底部條目指針258且更新線程110的頂部條目指針238 來要求條目220。線程112的指針也可經更新以反映條目220的「損失」，如參看圖6描述。 線程110可繼續以此方式要求條目直到達到其共享堆棧105的公平共享份額為止。
圖5說明多個線程之間的共享堆棧存取。如圖5中說明，因為線程112在其共享堆 棧105的自身部分內纏繞(即，其堆棧頂部指針268在其堆棧底部指針280下方)，所以線 程110可要求來自由線程112利用的堆棧條目中部的條目而不是來自由線程112利用的堆 棧條目底部的條目。這可導致線程112損失位於其堆棧中部的堆棧條目220而不是來自其 堆棧底部的堆棧條目。因此，線程112的堆棧可在條目218下方損壞。因此，堆棧底部指針 256可移動到條目218，如圖6中說明。因此，線程可根據其需求動態存取共享堆棧105，只 要存在足夠的條目。在條目變得缺乏的情況下，線程可放棄條目以實現公平堆棧利用(例 如，根據公平策略)。
如圖5中說明，線程112可「擁有」條目214-220且可「利用」條目216-220和條 目214-274。因此，當線程110要求條目220時，條目220由線程112 「擁有」且「利用」。
參看圖6，描繪系統200的另一特定說明性實施例，包含共享堆棧105以及處於與 圖5中所描繪不同的處理狀態的三個線程108、110和112。舉例來說，線程110已要求並覆寫線程112的條目。
線程112可擁有共享堆棧105的條目，從虛線270 (邏輯上從頂部條目指針252指 出)限定的214到虛線280 (邏輯上從底部條目指針258指出)限定的條目218。線程112 可能已將條目220丟失到線程110。因此，在圖6中說明的特定實施例中，線程112可從其 共享堆棧105的「經利用」部分的中部丟失條目220。線程112的堆棧底部指針256可已經 從指向274(例如，如圖5中說明)更新為指向新底部條目218。
類似地，線程110可擁有共享堆棧105的條目，由條目220 (由邏輯上從頂部條目 指針238指出的線276指示)限定且纏繞在堆棧105周圍以包含條目210和212 (由邏輯 上從底部條目指針244指出的線286指示)。線程110因此擁有條目210、212、220和222。 線程112已將條目220丟失到線程110。
根據特定實施例，丟失有效條目220 (例如，位於堆棧底部指針256與堆棧頂部指 針254之間的條目)的線程112可使比丟失的條目220老的任何條目無效。為此，線程112 可將其堆棧底部指針256設定為指向與新遞增的底部條目指針258相同的條目。
圖6說明共享堆棧105由多個線程存取，在此期間一個線程可要求並覆寫另一線 程所擁有的條目。可通過修改線程指針而不移動共享堆棧105內的條目來要求所述條目。 共享堆棧105可根據線程的當前需求在線程之間動態分配，這可促進有效的堆棧利用。
圖7說明管理處理器的多個線程共享的堆棧的方法700的特定說明性實施例的流 程圖。如本文所描述，說明性方法700可由圖1的系統100或圖2的系統200執行。
在702處，可將共享堆棧的第一部分分配給第一線程。舉例來說，圖1的共享堆棧 105的第一部分116可分配給第一線程108。為進一步說明，第一線程108可執行需要共享 堆棧105的額外空間的過程。第一線程108的指針162可指向共享堆棧105的第一部分 116 (例如，額外條目)以獲得對第一部分116的控制。
在704處，可將共享堆棧的第二部分分配給第二線程。舉例來說，可將圖1的共享 堆棧105的第二部分118分配給第二線程110。為進一步說明，第二線程110可執行需要共 享堆棧105的額外空間的過程。第二線程110的指針164可指向共享堆棧105的第二部分 118以獲得對第二部分118的控制。
在706處，可將共享堆棧的第三部分分配給第三線程。舉例來說，可將圖1的共享 堆棧105的第三部分120分配給第三線程112。為進一步說明，第三線程112可執行需要共 享堆棧105的額外空間的過程。第三線程112的指針166可指向共享堆棧105的第三部分 120以獲得對第三部分120的控制。
在708處，可使用共享堆棧來預測返回地址。舉例來說，可使用圖1的共享堆棧 105來預測包含在返回數據134中的函數返回地址。
應注意，儘管圖7的方法700描繪在對共享堆棧的任何使用之前將共享堆棧的部 分分配給多個線程，但此排序是僅出於說明性目的且不應認為具有限定性。被分配得到共 享堆棧的一部分的任何線程可開始使用其所分配部分而不管何時其它線程被分配得到共 享堆棧的其它部分。
圖7因此展示管理由處理器的多個線程共享的堆棧的方法700。根據特定實施例， 可根據線程請求動態分配共享堆棧的條目。所述動態分配可以轉化為增加的堆棧效率、裸 片上的較小空間需求以及改進的性能的方式促進分支預測。
圖8說明實現對共享堆棧的多線程存取的方法800的特定說明性實施例的流程 圖。如本文所描述，說明性方法800可由圖1的系統100或圖2的系統200執行。
在802處，可在存儲器的一部分內形成共享堆棧。舉例來說，可在存儲器104內形 成圖1的共享堆棧105。
在804處，可動態分配共享堆棧的第一部分和第二部分。舉例來說，可將圖1的共 享堆棧105的第一部分116動態分配給第一線程108。為進一步說明，第一線程108可執行 需要共享堆棧105的額外空間的過程。第一線程108的指針162可指向共享堆棧105的第 一部分116 (例如，額外條目)以獲得對第一部分116的控制。類似地，可將圖1的共享堆 棧105的第二部分118分配給第二線程110。為進一步說明，第二線程110可執行需要共 享堆棧105的額外空間的過程。第二線程110的指針164可指向共享堆棧105的第二部分 118以獲得對第二部分118的控制。
在806處，可調整第一部分或第二部分或兩者的大小。舉例來說，可根據第一線程 108的請求動態調整第一部分116的大小。第一線程108的指針162可指向第一部分116 的條目以縮減或增長第一部分116從而滿足所述請求。類似地，可根據第二線程110的請 求動態調整第二部分118的大小。第二線程110的指針164可指向第二部分118的條目以 縮減或增長第二部分118從而滿足所述請求。
或者，在808處，可固定第一部分、第二部分或兩者的大小。舉例來說，可固定圖1 的第一部分116、第二部分118或兩者的大小。為進一步說明，可將線程108、110、112和114 中的一者或一者以上的指針162-168 (例如，頂部條目指針和底部條目指針)設定為特定固 定值。所述固定值可經選擇使得共享堆棧105在線程108、110、112和114之間同等分割。
在810處，可根據公平策略限制分配給第一線程的第一部分的大小。舉例來說，可 根據圖1的公平策略140限制分配給第一線程108的第一部分116的大小。為進一步說明， 可基於與第一部分116相關聯的條目的最大數目和共享堆棧105的使用百分比中的至少一 者來限制第一部分116的大小。舉例來說，當第一線程108已滿足或超過公平共享份額閾 值時，公平策略140可限制第一部分116的大小和第一線程106可存取的相關聯條目數目。 可通過將共享堆棧105中的條目總數除以當前作用中線程108、110、112和114的數目來確 定公平共享份額閾值。
在812處，可利用處理器執行第一線程和第二線程。舉例來說，多線程處理器核心 106中的一者可執行第一線程108和第二線程110。
在814處，可允許第一線程相對於共享堆棧的第一部分的元素推送或彈出返回地 址。舉例來說，可允許第一線程108在第一部分116的數據元素124中的一者處執行返回 地址的彈出136或推送138。
在816處，可允許第二線程相對於共享堆棧的第二部分的元素執行返回地址的推 送或彈出。舉例來說，可允許第二線程110在第二部分118的第二數據元素126處執行返 回地址的彈出136或推送138。
在818處，可使用第一線程覆寫第二部分內的數據元素。舉例來說，可使用第一線 程108覆寫第二部分118的第二數據元素126。為了說明，第一線程108可執行推送138， 推送138致使覆寫第二部分118中的最老條目。
圖8因此說明在多個線程上共享堆棧存取的方法800。所述方法包含根據每一線程的當前請求動態分配對共享堆棧的存取。可由線程通過操縱屬於線程的指針來獲取和覆 寫共享堆棧的條目。因為更新線程指針而不是移動存儲在共享堆棧內的地址條目，所以可 減少處理和功率消耗。並且，實現等效性能所需的較少堆棧條目數目可進一步促進裸片上 的較小空間需求。改進的存儲器分布可進一步增加堆棧性能。
參看圖9，描繪包含實施共享堆棧964的多線程存取的邏輯的電子裝置的特定說 明性實施例的框圖，且其一般表示為900。裝置900包含處理器，例如多線程處理器910，其 耦合到存儲器932。多線程處理器910包含可由多個線程存取的共享堆棧964，例如返回堆 棧。在說明性實例中，多線程處理器910包含圖1-6中的一者或一者以上中描繪的系統，且 可執行圖7和8的方法中的一者或一者以上，或其任何組合。應注意，儘管圖9中說明的實 施例描繪可攜式電子裝置，但如本文揭示的共享堆棧部分的分配可在包含處理器的任何裝 置處實施。舉例來說，裝置900或其某一部分可改為集成到機頂盒、音樂播放器、視頻播放 器、娛樂單元、導航裝置、通信裝置、個人數字助理(PDA)、固定位置數據單元、計算機、服務 器，或具有擁有返回地址堆棧的至少一個處理器的任何其它裝置中。
存儲器932可為存儲指令950的計算機可讀有形媒體，指令950由計算機的執行 導致共享堆棧的第一部分向第一線程的分配。舉例來說，指令950可由多線程處理器910 執行，從而致使將共享堆棧964的第一部分分配給第一線程。指令950可進一步經執行從 而致使將共享堆棧964的第二部分分配給第二線程。
圖9還展示耦合到多線程處理器910且耦合到顯示器928的顯示器控制器926。 編碼器/解碼器(CODEC) 934也可耦合到多線程處理器910。揚聲器936和麥克風938可耦 合到 CODEC 934。
圖9還指示無線控制器940可耦合到多線程處理器910且耦合到無線天線942。 在特定實施例中，多線程處理器910、顯示器控制器926、存儲器932、C0DEC 934和無線控制 器940包含在系統級封裝或晶片上系統裝置922中。在一特定實施例中，輸入裝置930和電 源944耦合到晶片上系統裝置922。此外，在特定實施例中，如圖9中所說明，顯示器928、 輸入裝置930、揚聲器936、麥克風938、無線天線942及電源944在晶片上系統裝置922外 部。然而，顯示器928、輸入裝置930、揚聲器936、麥克風938、無線天線942及電源944中 的每一者可耦合到晶片上系統裝置922的組件，例如接口或控制器。
所屬領域的技術人員將進一步了解，可將結合本文所揭示的實施例而描述的各種 說明性邏輯塊、配置、模塊、電路和算法實施為電子硬體、計算機軟體或兩者的組合。上文已 大體依據其功能性描述各種說明性組件、塊、配置、模塊、電路和算法。所述功能性是實施為 硬體還是軟體取決於特定應用及施加於整個系統的設計約束。所屬領域的技術人員可針對 每一特定應用以不同方式實施所描述功能性，但所述實施決策不應被解釋為導致偏離本發 明的範圍。
結合本文中所揭示的實施例描述的方法或算法的指針可直接體現於硬體中、體現 於由處理器執行的軟體模塊中或體現於兩者的組合中。軟體模塊可駐留在隨機存取存儲器 (RAM)、快閃記憶體、只讀存儲器(ROM)、可編程只讀存儲器(PROM)、可擦除可編程只讀存儲 器(EPROM)、電可擦除可編程只讀存儲器(EEPROM)、寄存器、硬碟、可裝卸式盤、壓縮光碟只 讀存儲器(CD-ROM)，或此項技術中已知的其它形式的存儲媒體中。示範性存儲媒體耦合到 處理器使得處理器可從存儲媒體讀取信息和將信息寫入到存儲媒體。在替代方案中，存儲媒體可與處理器成一體式。處理器及存儲媒體可駐留在專用集成電路(ASIC)中。ASIC可 駐留在計算裝置或用戶終端中。在替代方案中，處理器及存儲媒體可作為離散組件駐留在 計算裝置或用戶終端中。
提供對所揭示實施例的先前描述以使所屬領域的技術人員能夠製作或使用所揭 示的實施例。所屬領域的技術人員將容易了解對這些實施例的各種修改，且本文界定的原 理可在不脫離本發明的範圍的情況下應用於其它實施例。因此，本發明無意限於本文中所 展示的實施例，而是將賦予本發明與如由所附權利要求書界定的原理和新穎特徵一致的可 能的最廣範圍。
權利要求
1.一種設備，其包括 共享堆棧；以及 控制器，其可操作以選擇性地將所述共享堆棧的第一部分分配給第一線程，且選擇性地將所述共享堆棧的第二部分分配給第二線程。
2.根據權利要求1所述的設備，其中所述第一部分不與所述第二部分鄰接。
3.根據權利要求1所述的設備，其中所述第一部分與所述第二部分鄰接。
4.根據權利要求1所述的設備，其中所述共享堆棧選自由硬體堆棧和隨機存取存儲器RAM組成的群組。
5.根據權利要求1所述的設備，其進一步包括處理器，所述處理器包含經配置以產生與所述共享堆棧相關聯的堆棧操作請求的多線程處理器核心。
6.根據權利要求1所述的設備，其中所述控制器操作以響應於堆棧操作請求。
7.根據權利要求6所述的設備，其中所述堆棧操作請求包含推送和彈出中的至少一者。
8.根據權利要求6所述的設備，其中所述堆棧操作請求包含函數返回地址。
9.根據權利要求1所述的設備，其中所述第一線程覆寫所述第二部分內的數據元素。
10.根據權利要求1所述的設備，其中所述第一部分和所述第二部分是動態分配的。
11.根據權利要求1所述的設備，其中所述控制器包含 底部條目指針，其經配置以指向所述第一線程經配置以寫入到的所述共享堆棧的最底部條目； 頂部條目指針，其經配置以指向所述第一線程經配置以寫入到的所述共享堆棧的最頂部條目； 堆棧頂部指針，其經配置以指向與所述第一線程相關聯的所述共享堆棧的最近寫入的條目；以及 堆棧底部指針，其經配置以指向與所述第一線程相關聯的所述共享堆棧的最老有效條目。
12.根據權利要求1所述的設備，其中所述控制器包含經配置以指示所述第一線程是否正執行過程的線程作用中狀態位。
13.根據權利要求1所述的設備，其中所述控制器包含經配置以指示是否使用與所述第一線程相關聯的所述共享堆棧的條目的空位。
14.根據權利要求1所述的設備，其中所述控制器包含經配置以指示所述第一線程已在所述共享堆棧內纏繞的纏繞堆棧位。
15.根據權利要求1所述的設備，其中所述控制器經配置以預測函數返回地址，其中第一指令確定所述返回地址，且其中共享堆棧未中提示第二指令確定所述函數返回地址。
16.根據權利要求1所述的設備，其進一步包括選自由機頂盒、音樂播放器、視頻播放器、娛樂單元、導航裝置、通信裝置、個人數字助理PDA、固定位置數據單元和計算機組成的群組的裝置，所述控制器和所述存儲器中的至少一者集成到所述裝置中。
17.—種管理由處理器的多個線程共享的堆棧的方法，所述方法包括 將共享堆棧的第一部分分配給第一線程；以及 將所述共享堆棧的第二部分分配給第二線程。
18.根據權利要求17所述的方法，其進一步包括使用所述第一線程覆寫所述第二部分內的數據元素。
19.根據權利要求17所述的方法，其進一步包括允許所述第一線程相對於所述共享堆棧的所述第一部分的元素進行推送和彈出返回地址這兩個操作中的至少一者。
20.根據權利要求19所述的方法，其進一步包括允許所述第二線程相對於所述共享堆棧的所述第二部分的元素進行推送和彈出返回地址這兩個操作中的至少一者。
21.根據權利要求17所述的方法，其進一步包括在存儲器的一部分內形成所述共享堆棧。
22.根據權利要求17所述的方法，其進一步包括使用所述共享堆棧來預測返回地址。
23.根據權利要求17所述的方法，其進一步包括動態分配所述第一部分和所述第二部分。
24.根據權利要求17所述的方法，其進一步包括調整所述第一部分和所述第二部分中的至少一者的大小。
25.根據權利要求17所述的方法，其進一步包括固定所述第一部分和所述第二部分中的至少一者的大小。
26.根據權利要求17所述的方法，其進一步包括根據公平策略限制分配給所述第一線程的所述第一部分的大小。
27.根據權利要求26所述的方法，其中根據所述公平策略限制所述第一部分的所述大小包括基於與所述第一線程相關聯的最大條目數目和所述共享堆棧的使用百分比中的至少一者限制所述第一部分的所述大小。
28.一種存儲可由計算機執行的指令的計算機可讀有形媒體，所述指令包括 可由所述計算機執行以將共享堆棧的第一部分分配給第一線程的指令；以及 可由所述計算機執行以將所述共享堆棧的第二部分分配給第二線程的指令。
29.根據權利要求28所述的計算機可讀有形媒體，其中所述指令可由集成在一裝置中的處理器執行，所述裝置選自由機頂盒、音樂播放器、視頻播放器、娛樂單元、導航裝置、通信裝置、個人數字助理PDA、固定位置數據單元和計算機組成的群組。
全文摘要
一種管理由處理器的多個線程共享的堆棧的系統和方法包含將共享堆棧的第一部分分配給第一線程，以及將所述共享堆棧的第二部分分配給第二線程。
文檔編號G06F9/38GK103003791SQ201180034701
公開日2013年3月27日 申請日期2011年7月15日 優先權日2010年7月16日
發明者史蒂芬·R·香農, 蘇雷什·K·文庫馬漢提, 羅伯特·A·萊斯特 申請人:高通股份有限公司