This preview shows page 1-2-3-4-5-6-7-52-53-54-55-56-57-58-59-105-106-107-108-109-110-111 out of 111 pages.
Slide 1Grade School Again: A Parallel Perspectivea questiona similar questionWarming up thinking about parallelismDot productsSlide 7Slide 8Parallel dot productsBinary treeSlide 11Not enough people?Another example: Matrix-vector multiplicationsHow much time in parallel?Back to our question…How to add 2 n-bit numbers.Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23If n people agree to help you add two n bit numbers, it is not obvious that they can finish faster than if you had done it yourself.Slide 25Plus/Minus Binary (Extended Binary)Slide 27Slide 28n people can add two n-trit plus/minus binary numbers in constant time!An Addition Party to Add 110-1 to -111-1An Addition PartySlide 32Pass LeftAfter passing leftPassing left againAfter passing left againSlide 37StrategySlide 39Slide 40Slide 41Grade School AdditionSlide 44Ripple-carry adderLogical representation of binary: 0 = false, 1 = trueSlide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Yes, but first a neat idea…Carry-Save AdditionSlide 59Slide 60Slide 61Grade School MultiplicationWe need to add n 2n-bit numbers: a1, a2, a3,…, anSlide 64Slide 65So let’s go back to the problem of adding two numbers. In particular, if we can add two numbers in O(log n) parallel time, then we can multiply in O(log n) parallel time too!If we knew the carries it would be very easy to do fast parallel additionWhat do we know about the carry-out before we know the carry-in?Slide 69Slide 70Slide 71Idea #1: do this calculation first.Slide 73Slide 74Idea #2:Idea #2 (cont):Just using the fact that we have an Associative, Binary OperatorExamples of binary associative operatorsSlide 79Prefix Sum ProblemPrefix Sum example when + = additionExample circuitry (n = 4)Divide, conquer, and glue for computing yn-1Slide 84The above construction had small parallel run-timeSize of Circuit (number of gates)Sum of SizesRecursive Algorithm n items (n = power of 2)Slide 89Slide 90Parallel time complexitySizeSlide 93Putting it all together: Carry Look-Ahead AdditionSlide 95Putting it all together: multiplicationSlide 97Slide 98Slide 99And this is how addition works on commercial chips…..Slide 101Slide 102Slide 103Slide 104Slide 105Slide 106Brent’s LawSlide 108If n2 people agree to help you compute the GCD of two n bit numbers, it is not obvious that they can finish faster than if you had done it yourself.Slide 110No one knows.Slide 11215-251Great Theoretical Ideas in Computer ScienceGrade School Again:A Parallel Perspectivea questionIf a man can plough a field in 25 days, how longdoes it take for 5 men to plough the same field?5 daysa similar questionIf a processor can add two n-bit numbers in n microseconds, how long does it take for n processors to add together two n-bit numbers?hmm…Warming up thinking about parallelismDot productsa = (4 5 -2 1)b = (1 -3 3 7)Dot product of a and ba-b = 4.1 + 5.(-3) + (-2).3 + 1.7 = 10Also called “inner product”.In general, a-b =Dot productsIf we can add/multiply two numbers in time C, how long does it take to compute dot products for n-length vectors?n multiplicationsn-1 additionshence, C*(2n-1) time.simplifying assumption for nowDot productsWhat if n people decided to compute dot productsand they worked in parallel?Modeling decision:what are people allowed to do in parallel?Assume they have shared memoryCan read same location in memory in parallelEach location in memory can be written to by only one person at a time.Can write to different locations in memory simultaneouslyParallel dot productsWhat if n people decided to compute dot productsand they worked in parallel?All the pairwise products can be computed in parallel! (1 unit of time)How to add these n products up fast?Binary treeParallel dot productsWhat if n people decided to compute dot productsand they worked in parallel?All the pairwise products can be computed in parallel! (1 unit of time)How to add these n products up fast?Can add these numbers up in log2 n roundsHence dot products take log2 n +1 time in parallel.Not enough people?What if there were fewer than n people?Another example:Matrix-vector multiplicationsSuppose we were given a m*n matrix Aand a n-length vector xHow much time does it take to compute Ax?How much time in parallel?Since just m dot product computationsand all of them can be done in parallelSo if we had m*n people, we could compute the solution to Ax in O(log2 n) timeBack to our question…If a single processor can add two n-bit numbers in n microseconds, how long does it take n processors to add together two n-bit numbers?How to add 2 n-bit numbers. ** ** ** ** ** ** ** ** ** ** ** +How to add 2 n-bit numbers. *** ** ** ** ** ** * ** ** ** ** ** +How to add 2 n-bit numbers. *** ** ** ** ** * ** * *** ** ** ** ** +How to add 2 n-bit numbers. *** ** ** ** * ** * *** * *** ** ** ** ** +How to add 2 n-bit numbers. *** ** ** * ** * *** * *** * *** ** ** ** ** +How to add 2 n-bit numbers. *** * *** * *** * *** * *** * *** * *** * *** * *** * *** *** * +* *How to add 2 n-bit numbers. *** * *** * *** * *** * *** * *** * *** * *** * *** * *** *** * +* * Let k be the maximum time that it takes you to do Time = kn is proportional to nThe time grow linearly with input size. # of bits in numberstimeknIf n people agree to help you add two n bit numbers, it is not obvious that they can finish faster than if you had done it yourself.Is it possible to add two n bit numbers in less than linear parallel-time? Darn those carries.Plus/Minus Binary(Extended Binary)Base 2: Each digit can be -1, 0, 1, Example: 1 -1 -1 = 4 -2 -1 = 1Not a unique representation systemFast parallel addition is no obvious in usual binary. But it is amazingly direct in Extended Binary!Extended binary means base 2 allowing digits to be from {-1, 0, 1}. We can call each digit a “trit”.n people can add two n-trit plus/minus binary numbers in constant time!An Addition Party to Add 110-1 to -111-1-An Addition Party1-111101-1-1Invite n people to add two n-trit numbersAssign one person to each trit positionAn Addition Party012 1-2Each person should add the two input trits in their possession. Problem: 2 and -2 are not allowed in the final answer.Pass Left00-1-21If you have a 1 or a 2 subtract 2 from yourself and pass a 1 to the left. (Nobody keeps more than 0) Add in anything that
View Full Document
Unlocking...