| | | | | | Examples of application domains with long real-time requirements, where Beowulf systems might be relevant include weather forecasting, financial modeling/prediction, and scientific and engineering simulations. The common feature of all these computational activities is that the importance of the result of a single computation may be strongly dependent on the passage of time, e.g., a weather forecast's value plummets dramatically as the forecasted hour approaches. A large scientific calculation may be important enough to invest a year of computation, but it would be considerably more valuable if the result were available in a month. A dedicated 16-processor Beowulf system could easily make that kind of difference. | | | | | | | | | It is important to separate the effects of throughput and response time. If the motivation for parallelizing an application is to improve response time, then one must carefully consider the effect of other users on the system. If a 16-processor Beowulf is shared with a dozen other researchers, it will have almost no effect on response time, i.e., the time for any one researcher to complete a problem. All other things being equal, it would probably have been easier, and just as effective, for the researchers to run their problems on individual workstations. Of course, if the problems don't fit on a single workstation due to size constraints, then parallelization is indicated anyway. However, that is a separate consideration from improving response time. | | | | | | | | | 7.2 Broad Categories of Parallel Algorithms | | | | | | | | | Parallel algorithms can be categorized according to a number of criteria. While not strictly orthogonal, these criteria provide useful information about the structure and requirements of a particular method or algorithm. Some types of algorithms are more suitable for Beowulfs than others. Often, there are several algorithms or strategies available to solve any particular problem, and tradeoffs must be weighed to determine which is most appropriate. | | | | | | | | | 7.2.1 Regular and Irregular | | | | | | | | | Regular algorithms use data structures that fit naturally into rectangular arrays. Irregular algorithms require more complicated data structures, e.g., indirect addressing, trees, linked lists, graphs, hash-tables, etc.. Regular structures are often easier to partition into separate parallel processes. For example, rectangular arrays can be split up into blocks and distributed to processors. The data residing in each processor is still a rectangular block, and hence the code that works on it often needs only minor modification to work in parallel. | | | | |
