View Question
Q: Computer Architecture ( Answered,   2 Comments )
 Question
 Subject: Computer Architecture Category: Computers Asked by: bkk-ga List Price: \$10.00 Posted: 01 Oct 2002 09:12 PDT Expires: 31 Oct 2002 08:12 PST Question ID: 71206
 ```1.2[20/10/10/10/15] <1.6> In this exercise, assume that we are considering enchancing a machine by adding vector hardware to it. When a computation is run vector mode on the vector hardware. It is 10 times faster than the normal mode of execution. We call the percentage of time that could be spent using vector mode the percentage of vectorization. Vectors are discussed in Appendix G. but you don't need to know anything about how thay work to answer this question! a. [20]<1.6> Draw a graph that plots the speedup as a percentage of the computation performed in vector mode, Lebal the y-axis "net speedup" and label the x-axis "Percent vectorization" b. [10]<1.6> What percentage of vectorization is needed to achieve a speedup of 2? c. [10]<1.6> What percentage of the computation run time is spent in vector mode if a speedup of 2 is achieved? d. [10]<1.6> What percentage of vectorization is need to achieve one-half the maximum speedup attainble from using vector mode? e. [15]<1.6> Suppose you have measured the percentage of vectorization for programs to be 70%. The hardware design group says they can double the speed of the vector hardware with a significant additional engineering investment. You wonder whether the compiler crew could increase the use of vector mode as another approach to increasing performance. How much of an increase in the percentage of vectorization(relative to current usage) would you need to obtain the same performance gain as doubling vector hardware speed? Which investment would you recommend?``` Request for Question Clarification by rbnn-ga on 03 Oct 2002 01:56 PDT ```Hi there, I just wanted to check that you did intend for the vector hardware to run 10 times faster and not 20 times faster - (20 times faster seems for some reason like the standard formulation of this problem).```
 Answer
 Subject: Re: Computer Architecture Answered By: rbnn-ga on 03 Oct 2002 22:39 PDT
 ```Thank you for posing this question. Issues about speedup and vectorization are often quite controversial and emotional; I used to do a lot of work with vectorized and parallel codes, and researchers (and marketers) would argue endlessly about how much speedup was achieved. I did not receive a clarification as to whether you intended a speedup of 10 or 20 in vectorizable code. Therefore, I will simply answer your question as stated. If you would like it re-solved for a speedup of 20 instead of 10, just use the "request clarification" button to do so. In this particular case, the solution to your problem, with the speedup for vectorized code of 10 and not 20, is available in pdf from: http://www.cs.ucf.edu/courses/cda5106/summer02/hw1_sol.pdf . You need a pdf reader to access this, which you can get here: http://www.adobe.com/products/acrobat/readstep.html . This solution is useful also for defining the key terms involved. a: Let S be the net speedup, let V be the speedup for vectorized code, and let F be the fraction of code that is vectorizable, and let P be the speedup on vectorizable code. Then S is the time_without_vectorization/time_with_vectorization . Suppose the time without vectorization is 1 . Then using vectorization, 1-F of the code runs at the same speed, taking time 1-F, and F runs at time F/P. Hence the total time for the vectorizing code is 1-F + (F/P). The net speedup is then: 1 ------- 1-F+(F/P) Here we are using a value of P of 10, so the speedup is: 1 ------- 1-F+(F/10) This can be rewritten: 1/(1-.9F) Now remember that F is going to be the percentage of vectorization divided by 100, so if G is the percentage of vectorization, the graph is: Speedup = 1/(1-.009 G) G here ranges from 0% to 100%. You can graph this I assume yourself using your favorite graphing software. The X axis should be "precent vectorization" and the Y-axis should be Speedup (as in the solution link posted above). Specific values are: Percent Vectorization Speedup ------------------------------------------- 0 1 .1 1.0009 1 1.0091 10 1.0989 50 1.8 90 5.2632 100 10 Oddly enough, an example in a page on how to use gnuplot includes this graph! I used google's cache of the web page, which was unavailable, at: http://216.239.51.100/search?q=cache:BqeynDIQvEMC:www.cs.virginia.edu/helpnet/Authoring_Tools/gnuplot/+gnuplot+percent*+vectorization&hl=en&ie=UTF-8 to see this. b: Speedup = 1/(1-.009 G) 1-.009G = 1/Speedup G=(1-1/Speedup)/.009 For speedup of 2, we get G=(1-1/2)/.009 = .5/.009 55.5556 thus a percent vectorization of 55.6% will be necessary to achieve a speedup of 2. c: If a speedup of 2 is achieved, then 55.6% of the code is vectorized. Suppose the original code takes 100 seconds. Then 100-55.6 = 44.4 % of the code will run unvectorized, which will take 44.4 seconds. We know, since a speedup of 2 is achieved that the total run time is 50 seconds. Hence, 50-44.4=5.6 seconds are spent in vectorized code. Thus, 5.6% of the runtime will be spent running vectorized code. d: The maximum speedup is 10, as we saw above, so half the maximum speedup is 5. As in part b, we have: G=(1-1/Speedup)/.009 = .8/.009 =88.89% e: Let P' be the new speedup. If we doubled hardware speed, then P'=20 so that speedup is 1/(1-F+F/20) Consider a program that runs unoptimized in 100 seconds. In the current hardware/compiler configuration, the speedup is: 1/(1-.7+.7/10) = 1/(.3+.07) = 2.7 Hence, this program takes 100/2.7 seconds, or 37 seconds to run currently. On the other hand if we use the hardware speedup, then the speedup is: 1/(1-.7+.7/20) = 2.9851 So that the total time is: 100/2.9851 = 33.5 seconds . The percent improvement is Now, we want to know, what percent of vectorization would result in such a speedup with the current hardware? We just plug in our formula from part b: G=(1-1/Speedup)/.009 G= (1-1/(2.9851)/.009) = 73.9 % Originally our percent vectorization was 70%. Hence, the percent increase in vectorization is: 3.9/70 = 5.5 % So trying to improve the compiler a little bit seems like a natural choice, and is the answer they are looking for. (In real life, things are more complicated. For example, sometimes "important" codes, codes that rich customers really need or want or will pay to have sped up, are the most highly vectorizable; and it is more important to speed these up than to speed up other codes. For example, suppose you are a supercomputer vendor who sells 10 machines each year at a cost of 20 million dollars each. If two of your customers are using your machines to do a particular computational fluid dynamics simulation that is 99.9% vectorizable, then maybe investing in hardware IS the best choice. Furthermore, remember that those customers who really want to improve vectorizability can often tweak codes by hand; but the fluid dynamics people have already done all the hand-tuning to increase vectorization they need).``` Clarification of Answer by rbnn-ga on 03 Oct 2002 22:54 PDT ```I forgot to mention my search strategy. I used the "*" feature of google searches and searched on: percent* vectorization I also did searches on percentage vectorization There are many hits on the problem, but I only found the single hit with the problem solution on the web.```
 Comments
 Subject: Re: Computer Architecture From: secret901-ga on 01 Oct 2002 10:49 PDT
 `http://216.239.33.100/search?q=cache:UMvgavXVHPAC:www.cis.umassd.edu/~eeberbach/courses/cis570/assignments/assign1.html+%22Suppose+you+have+measured+the+percentage+of%22&hl=en&ie=UTF-8`
 Subject: Re: Computer Architecture From: ericynot-ga on 01 Oct 2002 15:41 PDT
 `http://www.cs.utexas.edu/users/fussell/cs352/Homework/Homework1.html`
 Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service. If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for

 Google Home - Answers FAQ - Terms of Service - Privacy Policy