Perceptron Branch Prediction with Separated T/NT Weight Tables

Perceptron Branch Prediction with Separated T/NT Weight Tables

Perceptron Branch Prediction with Separated T/NT Weight Tables Guangyu Shi and Mikko Lipasti University of Wisconsin-Madison June 4, 2011 Perceptron Branch Prediction Perceptron branch predictor [Jimnez & Lin, 2001] 7 6 4 5 -8 -9 -3

-2 -5 -4 3 -2 PC History * 1 -1 1 -1

-1 Y N >=0 Taken Not-taken Outcome: Not-taken Intuition A code example: // x is an unknown value if (x>1000) // Branch A { /* do something */}

To predict branch B: if (x>500) // Branch B { /* do something else taken*/} for sure If A is taken, B is also If A is not taken, do not know the outcome of B If A is taken at certain frequency, then whenever A is nottaken, B will be predicted not-taken. Intuition

Perceptrons can represent positive or negative correlations between branch B and past branches. They cannot strengthen 1(2) without strengthen 4(3), or vice versa NT T 2 3 1 T 4 NT // x is an unknown value if (x>1000) // Branch A { /* do something */}

if (x>500) // Branch B { /* do something else */} SWP: Separated Weight Predictor Separate T/NT weight tables Prediction Algorithm: function predict: boolean begin sum := 0; index := hash (PC); for i in 1 to ghl do if GHR[i] = true then sum := sum + WT[index, i]; else sum := sum + WNT[index, i]; end for predict := (sum>=0);

end 1 WT WNT 0 1 1 0 SWP: Separated Weight Predictor Update Algorithm function update begin if |sum|

br_taken index := hash (PC); for i in 1..ghl do if {GHR[i] , br_taken} = {1, 1} then WT[index,i] := WT[index,i] +1; if {GHR[i] , br_taken} = {1, 0} then WT[index,i] := WT[index,i] -1; if {GHR[i] , br_taken} = {0, 1} then WNT[index,i] := WNT[index,i] +1; if {GHR[i] , br_taken} = {0, 0} then WNT[index,i] := WNT[index,i] -1; end for end if end 1 WT WNT 0

1 1 0 SWP: Separated Weight Predictor Capable of prediction some linearly inseparable branches even if path information is the same History Perceptron 1 -1(0) -3 -1

Prediction: -3 (-1) = -2 Not-taken SWP: Separated Weight Predictor Capable of prediction some linearly inseparable branches even if path information is the same History 1 -1(0) 1 -2 4 -1

SWP Prediction: 1+(-1) = 0 (Taken) SWP: Separated Weight Predictor Combined with other optimization schemes Piecewise linear branch prediction [Jimnez, 2005] Dynamic threshold from O-GEHL [Seznec, 2005] Bias weights are removed Implementation of SWP

Additional multiplexors (in parallel) No bitwise complement of weights needed Simulation Result Performance result of 11 traces out of 40 (in MPPKI) Optimization for space Space inefficient: 2x storage space of the regular perceptron predictor. Solution: Partially separated weight tables History 1 to h0 1 0 0 1 0

* PC WT 1 1 -1 1 -1 * W XOR Path History h0+1 to h WNT * 0 1 1 0 1 Optimization for space

Simulation result on branch prediction with partially separated weight tables (in MPPKI) Configuration for CBP-3 Final configuration: 3 different weight tables First 20 branches: separated weights, 1024 entries Next 16 branches: single weight, 1024 entries Last 29 branches: single weight, 512 entries Total history length: 65 Total size of the weight tables: 61.7KB

Future work Analyze how often is code example 1 executed Further reduce the storage budget by using adaptive encoding algorithm

Recently Viewed Presentations

  • The Silent Tsunami: Mental Health and Stress in the Workplace

    The Silent Tsunami: Mental Health and Stress in the Workplace

    The Silent Tsunami: Mental Health and Stress in the Workplace. Mental health issues and stress are a silent tsunami in the workplace, one that could engulf organizations in a myriad of productivity and profitability problems as well as legal liabilities...
  • Ancient Greek Olympics - Centennial School District

    Ancient Greek Olympics - Centennial School District

    Time Line of the 5-day event 1st Day 2nd Day 3rd Day 4th Day 5th Day Arena at Olympia The great arena at Olympia was the site for most of the events in the games. After years of training and...
  • American Imperialism - US History

    American Imperialism - US History

    American Imperialism: Latin America. Following the end of the Spanish-American War the United States was in an excellent position to take advantage of markets throughout Latin America US wanted to develop a trans-oceanic canal between the Atlantic and Pacific Ocean...
  • The Madrid Protocol: Key Benefits, Risks and Strategies

    The Madrid Protocol: Key Benefits, Risks and Strategies

    The Madrid Protocol: Key Benefits, Risks and Strategies. You would like to have your trademark protected in several countries, but realize that filing separate applications is both complicated and very expensive as the national or regional trademark laws regarding formalities...
  • Chapter 6 Mathematical Operations C++: LEARN BY DOING

    Chapter 6 Mathematical Operations C++: LEARN BY DOING

    Rule . of . thumb. Match the . l-value. with the . r-value. ... Type cast when the square root of integers is required. 6.8.2 The sqrtFunction - Example. ... The trigonometry function parameters are specified in radians. 6.9 Type...
  • SNMP - Simple Network Measurements Please!

    SNMP - Simple Network Measurements Please!

    Times New Roman Comic Sans MS Zapf Dingbats Monotype Sorts SchlSymbol Bold Arial Black Tahoma Arial Wingdings Times Symbol Contemporary Portrait Microsoft Equation Microsoft Graph Chart Network Tomography and Internet Traffic Matrices Matthew Roughan School of Mathematical Sciences University of...
  • CO324 - Computer Systems

    CO324 - Computer Systems

    the project was called GNU - a recursive acronym standing for "GNU's Not UNIX" History of UNIX - Part II. Stallman. The GNU logo. Stallman is still a majorcampaigner. The slide shows a photograph of a very hairy (long hair,...
  • What is a myth?

    What is a myth?

    What is a Fable? uses personification - animals, plants, forces of nature (ex: thunder), or objects with human-like characteristics. always has a moral, or lesson learned. will often have a trickster who learns a lesson. are passed down orally by...