Author |
Topic: Paralle programming (Read 450 times) |
|
howard roark
Full Member
Posts: 241
|
 |
Paralle programming
« on: Sep 26th, 2008, 8:47am » |
 Quote  Modify
|
Suppose there are p processors, where each processor starts with p and its processor number pid in local variables, 0 ≤ pid ≤ p − 1. There is an integer array V [0 : p−1], and you are to find the smallest i such that V [i] = 1, or return the value p if there is no such i. The answer should be stored in the integer variable firstone.
Each processor is a standard microprocessor with a small amount of local memory (not enough to store large arrays), and there is as much global memory as is needed. V and firstone are stored in shared memory.
Make sure you identify which variables are local (every processor has its own copy of
the variable, such as pid), and which ones are global (there is a single instance of the variable, accessible to
all, such as firstone). If k processors try to read from the same memory location at the same time then they
all get the correct value, but if they try to write to the same memory location at the same time then the result
can be arbitrary. However, if they write to different locations simultaneously then all of the memory locations
receive the correct values. If one processor is writing to a memory location while another is reading from it
then the processor trying to do the read operation may receive an arbitrary value. In the statement x = y, for
global variables x and y, the y is being read and the x is being written.
To assist you, there is a command barrier. No processor will execute any statements after the barrier instruction
until all of them have reached it. For example, if the code is
statement 1
barrier
statement 2
then no processor starts statement 2 until all have finished statement 1. Barriers are often time-consuming,
so use them as infrequently as possible, but asymptotic time is most important. E.g., if algorithm A has no
barriers and takes time (n), while algorithm B has many barriers but takes time (√n), then B is better.
However, if algorithm C also takes (√n) time and has only a few barriers, then C is best.
|
|
 IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print