Concept of Time elapsed and processors
Page 1 of 18 Replies  973 Views  Last Post: 12 April 2011  10:53 PM
#1
Concept of Time elapsed and processors
Posted 23 March 2011  07:42 PM
If I want to compute the average of 1000 numbers>>
a. If i can only do one thing at a time, how many time steps will this take? (Assume each
arithmetic operation, i.e., add, subtract, multiply, divide, takes one time step.)
My answer: Count the numbers, add them, sum/# of number so 3 steps?
b. Suppose that we have two processors? We still have to perform the same operations.
But how much elapsed time is now required? Describe how you will organize the
computation to get the answer that you give.
My answer: Not sure how i have to express elapsed time and how
c. Suppose that we have ten processors? Now how much elapsed time is required?
My answer: I am guessing less since there are more processors but again, dont know how to express it.
thanks for any help and your time.
Replies To: Concept of Time elapsed and processors
#2
Re: Concept of Time elapsed and processors
Posted 24 March 2011  07:17 AM
@b: It sounds like they are expressing "time" in steps.
#3
Re: Concept of Time elapsed and processors
Posted 24 March 2011  08:06 AM
modi123_1, on 24 March 2011  07:17 AM, said:
@b: It sounds like they are expressing "time" in steps.
i see okay. so 999 steps for adding one to another and then another step for dividing the sum by 1000. so total of 1000 steps.
For I said I would split down the number of steps halway between the two processors so now the elapsed time would be nearly cut in half.
For c) I said If we have ten processors, we could perform 100 steps on each and it would really cut down elapsed time to 10 times as less as doing it all on one processor.
does my logic make any sense to you or do you think there is a better way to put it
#4
Re: Concept of Time elapsed and processors
Posted 24 March 2011  08:18 AM
@ b & c: where's the count for getting the processors to put their information together?
#5
Re: Concept of Time elapsed and processors
Posted 24 March 2011  08:33 AM
modi123_1, on 24 March 2011  08:18 AM, said:
@ b & c: where's the count for getting the processors to put their information together?
ok so 999 steps for adding each one, 1000 steps for counting each of the 1000 numbers. and then 1 step for doing sum/count. so total of 2000 steps
) one processor could count each of the 1000 numbers and the other could add each one together to get sum, then the step to have both of them put their together, and then doing the sum/count so 2001 steps
c)) to put the information of ten processors would take 9 steps, in addition to 2000 steps that would be split across 10 processors(1000 for count, 999 for adding each other, and 1 for the division) so 2009
how about this
This post has been edited by recursive83: 24 March 2011  08:33 AM
#6
Re: Concept of Time elapsed and processors
Posted 25 March 2011  04:25 PM
Eg.
You carry lumber to your truck from the lumber yard, does it take you the same amount of time to carry the same amount of lumber alone or with help from your friends?
The purpose of a multiprocessor (or multicore) system is to split the load between the individual processors (or cores) thereby achieving a lower overall lapsed time, while still inherently doing the same maintaining the same amount of cycles done by a comparable single processor. It's the typical divideandconquer technique that's been in use for years.
#7
Re: Concept of Time elapsed and processors
Posted 26 March 2011  02:32 PM
recursive83, on 23 March 2011  08:42 PM, said:
If I want to compute the average of 1000 numbers>>
a. If i can only do one thing at a time, how many time steps will this take? (Assume each
arithmetic operation, i.e., add, subtract, multiply, divide, takes one time step.)
My answer: Count the numbers, add them, sum/# of number so 3 steps?
Processors work in 'Steps' sometimes called 'Ticks.' There are 10,000,000 ticks in a Second. But remember that EVERY action is a step, EVERY action, even down to each addition operation in the sum. See below.
In this case, the basic formula for average is: Sum( N1...NX ) / Y
That means, the processor has to do several things. This is how the problem should be approached.
1st: How many steps does it take to add a number? Let that answer be A.
2nd: Multiply A by Y and let that answer be B
3rd: Add 1 to B for division
Answer: B + 1 and let this answer be C
recursive83, on 23 March 2011  08:42 PM, said:
But how much elapsed time is now required? Describe how you will organize the
computation to get the answer that you give.
My answer: Not sure how i have to express elapsed time and how
Take however much time elapsed for C to happen and the time required to do all of the steps SHOULD be half of the time required to do C. Assuming that both systems are exactly the same of course.
recursive83, on 23 March 2011  08:42 PM, said:
My answer: I am guessing less since there are more processors but again, dont know how to express it.
thanks for any help and your time.
Same as above. Just that this time it will only take a TENTH of the time it took to complete C in the first question.
I'm assuming of course that when whoever assigned this to you used the word 'Time Step' they meant 'Tick.'
Does all of this make sense?
This post has been edited by ccubed: 26 March 2011  02:36 PM
#8
Re: Concept of Time elapsed and processors
Posted 30 March 2011  09:55 PM
ccubed, on 26 March 2011  02:32 PM, said:
recursive83, on 23 March 2011  08:42 PM, said:
If I want to compute the average of 1000 numbers>>
a. If i can only do one thing at a time, how many time steps will this take? (Assume each
arithmetic operation, i.e., add, subtract, multiply, divide, takes one time step.)
My answer: Count the numbers, add them, sum/# of number so 3 steps?
Processors work in 'Steps' sometimes called 'Ticks.' There are 10,000,000 ticks in a Second. But remember that EVERY action is a step, EVERY action, even down to each addition operation in the sum. See below.
In this case, the basic formula for average is: Sum( N1...NX ) / Y
That means, the processor has to do several things. This is how the problem should be approached.
1st: How many steps does it take to add a number? Let that answer be A.
2nd: Multiply A by Y and let that answer be B
3rd: Add 1 to B for division
Answer: B + 1 and let this answer be C
recursive83, on 23 March 2011  08:42 PM, said:
But how much elapsed time is now required? Describe how you will organize the
computation to get the answer that you give.
My answer: Not sure how i have to express elapsed time and how
Take however much time elapsed for C to happen and the time required to do all of the steps SHOULD be half of the time required to do C. Assuming that both systems are exactly the same of course.
recursive83, on 23 March 2011  08:42 PM, said:
My answer: I am guessing less since there are more processors but again, dont know how to express it.
thanks for any help and your time.
Same as above. Just that this time it will only take a TENTH of the time it took to complete C in the first question.
I'm assuming of course that when whoever assigned this to you used the word 'Time Step' they meant 'Tick.'
Does all of this make sense?
that's what i thought it meant by tick but yes it all makes sense now. thanks for taking the time to reply.
#9
Re: Concept of Time elapsed and processors
Posted 12 April 2011  10:53 PM
For the purpose of this answer, I refer you to the diagram of the Intel Nahalem microarchitecture found here. This shows you the stages in the processor, and depending on what instruction is being performed and whether it is register to register, memory to register or register to memory, gives an indication of how many microcode cycles are taken. There are some fifteen microcode stages that instruction and data have to pass through in order to achieve a result (these used to be known as the fetch, decode, execute and store cycles). Now with instruction prefetch, lookahead tables, branch prediction etc, the whole process of adding two numbers together becomes very difficult to predict. Intel's x8664 architecture has I believe four ALU (Arithmetic Logic Units) within each processor that can perform both arithmetic and logic operations simultaneously. This, multiplied by four separate processors would give 16 ALU's! On top of this (as if this was not enough), we have dual access memory and various levels of cache to deal with. It is no wonder chip manufacturers have stopped telling developers how may cycles each instruction takes.
Finally, after all that, the code to add your numbers together and the computation of the average would be running on one and only one processor at any given point in time. Adding more processors would not make any difference to the overall performance of this computation, so the question is somewhat pointless.
This post has been edited by Martyn.Rae: 12 April 2011  11:01 PM
