8 Replies - 930 Views - Last Post: 12 April 2011 - 10:53 PM

#1 recursive83  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 18-February 11

Concept of Time elapsed and processors

Posted 23 March 2011 - 07:42 PM

Couldn't find any other appropriate section to post this.

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Concept of Time elapsed and processors

#2 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 8374
  • View blog
  • Posts: 31,120
  • Joined: 12-June 08

Re: Concept of Time elapsed and processors

Posted 24 March 2011 - 07:17 AM

@a: I think you are missing some chunks there. Each time you add a number to a number is a step because it is an operation, right? That means counting each number is a step for each time you add to a bucket. Adding each number to each other is a step, right?

@b: It sounds like they are expressing "time" in steps.
Was This Post Helpful? 0
  • +
  • -

#3 recursive83  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 18-February 11

Re: Concept of Time elapsed and processors

Posted 24 March 2011 - 08:06 AM

View Postmodi123_1, on 24 March 2011 - 07:17 AM, said:

@a: I think you are missing some chunks there. Each time you add a number to a number is a step because it is an operation, right? That means counting each number is a step for each time you add to a bucket. Adding each number to each other is a step, right?

@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 B) 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
Was This Post Helpful? 0
  • +
  • -

#4 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 8374
  • View blog
  • Posts: 31,120
  • Joined: 12-June 08

Re: Concept of Time elapsed and processors

Posted 24 March 2011 - 08:18 AM

@a: You are missing the steps for counting.

@ b & c: where's the count for getting the processors to put their information together?
Was This Post Helpful? 0
  • +
  • -

#5 recursive83  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 18-February 11

Re: Concept of Time elapsed and processors

Posted 24 March 2011 - 08:33 AM

View Postmodi123_1, on 24 March 2011 - 08:18 AM, said:

@a: You are missing the steps for counting.

@ 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

B)) 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

Was This Post Helpful? 0
  • +
  • -

#6 GenHornet18  Icon User is offline

  • Darken the Radar

Reputation: 36
  • View blog
  • Posts: 629
  • Joined: 19-October 09

Re: Concept of Time elapsed and processors

Posted 25 March 2011 - 04:25 PM

Presumably an ideal situation is assumed (no cache misses, bus fails etc). Where is your logic that with 1 processor the total elapsed time is smaller then with 10 equivalent processors (or cores)? Are they all running in parallel and not being used simultaneously?

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 divide-and-conquer technique that's been in use for years.
Was This Post Helpful? 0
  • +
  • -

#7 ccubed  Icon User is offline

  • It's That Guy
  • member icon

Reputation: 153
  • View blog
  • Posts: 1,394
  • Joined: 13-June 08

Re: Concept of Time elapsed and processors

Posted 26 March 2011 - 02:32 PM

View Postrecursive83, on 23 March 2011 - 08:42 PM, said:

Couldn't find any other appropriate section to post this.

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

View Postrecursive83, on 23 March 2011 - 08:42 PM, said:

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


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.

View Postrecursive83, on 23 March 2011 - 08:42 PM, said:

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.


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

Was This Post Helpful? 0
  • +
  • -

#8 recursive83  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 18-February 11

Re: Concept of Time elapsed and processors

Posted 30 March 2011 - 09:55 PM

View Postccubed, on 26 March 2011 - 02:32 PM, said:

View Postrecursive83, on 23 March 2011 - 08:42 PM, said:

Couldn't find any other appropriate section to post this.

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

View Postrecursive83, on 23 March 2011 - 08:42 PM, said:

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


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.

View Postrecursive83, on 23 March 2011 - 08:42 PM, said:

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.


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.
Was This Post Helpful? 0
  • +
  • -

#9 Martyn.Rae  Icon User is offline

  • The programming dinosaur
  • member icon

Reputation: 540
  • View blog
  • Posts: 1,406
  • Joined: 22-August 09

Re: Concept of Time elapsed and processors

Posted 12 April 2011 - 10:53 PM

Machine architecture is very complex and all the answers with the exception of ccubed are way off the mark. This is due to developers perception of what happens within a processor, and how multi-processors operate. Let me explain.

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, look-ahead tables, branch prediction etc, the whole process of adding two numbers together becomes very difficult to predict. Intel's x86-64 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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1