Broadcasting Data
The method of broadcasting data depends on the configuration of the processors, but often writes information to memory, which is then accessed by the other processors, if the configuration is tightly coupled. In a CREW PRAM model (see PRAM model), the processor writes from data, and all of the processors can read the data at the same time. This is a very efficient way to pass data, if you are using a CREW PRAM model. If you are using an EREW PRAM model, the program becomes a sequential loop, and it looses all the power of parallelism, if you follow the same process as before. However if you change it so that each processor that reads the information, writes it back to memory in a different location, the following cycle, twice as many processors can read from memory. Therefore, after two passes through the loop, half of the processors will have read the data ( if the number of processors is a power of two), which means, after the third pass, all will have read the information. This results in O(log p) if p represents the number of processors.
Finding Min/Max Values in a List
The first step in finding a maximum or minimum is to perform a sequential pre-processing step to reduce the number of values to twice the amount of processors, unless this is already the case. Then, each processor takes two pieces of data from the list and compares them. They put the larger value back in memory. Each pass cuts in half the amount of processors needed to compare items and the amount of items. This method has a time of O(log N), and if we use N log N processors, it will result in a total cost of O(N), which is the same as the sequential version, but much faster.
