15 251 Great Theoretical Ideas in Computer Science Grade School Again A Parallel Perspective a question If a man can plough a field in 25 days how long does it take for 5 men to plough the same field 5 days a similar question If 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 parallelism Dot products a 4 5 2 1 b 1 3 3 7 Dot product of a and b a b 4 1 5 3 2 3 1 7 Also called inner product In general a b 10 Dot products If we can add multiply two numbers in time C how long does it take to compute dot products for n length vectors simplifying assumption for now n multiplications n 1 additions hence C 2n 1 time Dot products What if n people decided to compute dot products and they worked in parallel Modeling decision what are people allowed to do in parallel Assume they have shared memory Can read same location in memory in parallel Each location in memory can be written to by only one person at a time Can write to different locations in memory simultaneously Parallel dot products What if n people decided to compute dot products and 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 tree Parallel dot products What if n people decided to compute dot products and 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 rounds Hence dot products take log2 n 1 time in parallel Not enough people What if there were fewer than n people Another example Matrix vector multiplications Suppose we were given a m n matrix A and a n length vector x How much time does it take to compute Ax How much time in parallel Since just m dot product computations and all of them can be done in parallel So if we had m n people we could compute the solution to Ax in O log2 n time Back 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 n t i m e kn of bits in numbers The time grow linearly with input size If 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 1 Not a unique representation system Fast 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 Party 1 1 1 1 0 1 1 1 Invite n people to add two n trit numbers Assign one person to each trit position An Addition Party 0 2 1 1 2 Each person should add the two input trits in their possession Problem 2 and 2 are not allowed in the final answer Pass Left 0 1 1 0 2 1 If 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 is given to you from the right Nobody has more than a 1 After passing left 1 1 1 There will never again be any 2s as everyone had at most 0 and received at most 1 more 2 Passing left again 1 1 1 1 1 If you have a 1 or 2 add 2 to yourself and pass a 1 to the left Nobody keeps less than 0 0 After passing left again 1 0 1 0 0 No 2s anymore either Everyone kept at least 0 and received at most 1 1 1 1 1 0 1 1 1 0 1 1 0 0 Strategy To add two n bit binary numbers Consider them to be in extended binary EB no work required Sum them up to get an answer in EB constant parallel time Then convert them back to answer in binary how do we do this fast in parallel Is there a fast parallel way to convert an Extended Binary number into a standard binary number Both problems not quite obvious Sub linear time addition in standard Binary Sub linear time EB to Binary Let s reexamine grade school addition from the view of a computer circuit Grade School Addition 10111 1011111101 Grade School Addition c5c4c3c2 c 1 a4a3a2 a1 a0 b4b3b2 b1 b0 s1 Ripple carry adder c 5c 4c 3c 2 a4a3a2 b4b3b2 c1 a1 a0 b1 b0 s1 an 1 bn 1 cn a i bi ci 1 si ai b i a1 b1 ci sn 1 ci si a0 b0 0 c1 s1 s0 Logical representation of binary 0 false 1 true c 5c 4c 3c 2 c 1 a4a3a2 a1 a0 b4b3b2 b1 b0 s1 a i bi ci 1 ci si s1 a1 XOR b1 XOR c1 c2 a1 AND b1 OR a1 AND c1 OR b1 AND c1 Logical representation of binary 0 false 1 true c 5c 4c 3c 2 c 1 a4a3a2 a1 a0 b4b3b2 b1 b0 s1 a i bi ci 1 ci si ai AND bi AND ci AND XOR OR ci 1 ai bi OR ci si ci 1 XOR si Ripple carry adder 0 How long to add two n bit numbers Propagation time through the circuit will be n Circuits compute things in parallel We can think of the propagation delay as PARALLEL TIME Is it possible to add two n bit numbers in less than linear parallel time I suppose the EB addition algorithm could be helpful somehow Plus minus binary means base 2 allowing digits to be from 1 0 1 We can call each digit a trit n people can add 2 n trit plus minus binary numbers in constant time 1 1 1 1 0 1 1 1 Can we still do addition quickly in …
View Full Document
Unlocking...