Method for analyzing capacity of parallel processing systems

Details Method for analyzing capacity of parallel processing systems Method for analyzing capacity of parallel processing systems

1997-12-23

2001-07-24

Powell, Mark (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000

Reexamination Certificate

active

06266804

ABSTRACT:

TECHNICAL FIELD
The invention relates to the analysis of computer systems and, more particularly, to the analysis of the execution of application programs by parallel processing systems.
BACKGROUND OF THE INVENTION
As the capabilities of computer processors and data storage devices have expanded in recent years, the data sets which are being processed have also increased dramatically in size. Despite rapid improvements, the performance and capacity of a system are often limited by processor speed.
One solution to such limitations has been to divide processing tasks into pieces and have multiple processors operate simultaneously upon those pieces. This approach reduces the burden on each processor and allows tasks which are not interdependent to be performed at the same time, or in parallel. A system configured in this way, with multiple processors operating in parallel, is called a parallel processing system. For purposes of this discussion, parallel processing systems include any configuration of computer systems using multiple central processing units (CPUs), either local (e.g., multiprocessor systems such as SMP or MPP computers), or locally distributed (e.g., multiple processors coupled via LAN or WAN networks), or any combination thereof.
Parallel processing allows an application to perform the same overall task more quickly. Alternately, an application on a parallel processing system can process more data in the same amount of time than on a single processor system. With the improvements in performance and capacity parallel processing allows, there is a need to evaluate those characteristics when running an application on a parallel processing system, either in place or proposed, or the effect of variation in the amount of data on performance of an application running on a particular parallel processing system.
In order to help analyze the performance of an application on a system, a model is used which represents the components of the application and the system and their interaction with supplied data sets. Because of the generally linear nature of data flow through a computer system, graphs have been used to describe these systems. The vertices in a graph represent either data files or processes, and the links or “edges” in the graph indicating that data produced in one stage of processing is used in another.
The same type of graphic representation may be used to describe applications on parallel processing systems. Again, the graphs will be composed of data, processes, and edges or links. In this case, the representation captures not only the flow of data between processing steps, but also the flow of data from one processing node to another. Furthermore, by replicating elements of the graph (e.g., files, processes, edges), it is possible to represent the parallelism in a system.
FIG. 1
shows an example of a graph describing an application on a parallel processing system with three processors. The application performs essentially two tasks: a transformation and a sort. Initially, the data is divided into three sections, represented by a vertex INPUT PARTITION. Each section is sent to one of three different processors, as represented by three links
10
,
11
, and
12
. Each of the three processors performs one or more tasks on a corresponding data section. This allocation of tasks is represented by three sets of vertices, TRANSFORM
1
and SORT
1
, TRANSFORM
2
and SORT
2
, and TRANSFORM
3
and SORT
3
. That is, the first processor performs a transformation and then sorts its section of data (TRANSFORM
1
and SORT
1
) and so on. At the end, the data is aggregated together and output as a unified whole, represented by a vertex OUTPUT AGGREGATION.
It is very difficult, however, to predict and model the performance of applications on parallel processing systems. As with single processor systems, these predictions depend on the amount of data which must be processed and the resources required for that processing. However, in addition to information about CPU processing speeds and requirements, data set sizes, memory utilization, and disk usage, information about effective communication rates between processors and network performance becomes necessary. With multiple processors acting in parallel, possibly at different speeds and on different amounts of data, and interconnected by channels or links having different rates, the computations can become quite complex.
For example, many parallel system configurations are purchased based on the size of the database to be processed. An arbitrary rule of thumb is typically then applied to compute the number of processors required based on a ratio of processors to gigabytes of disk storage. This kind of over-simplification often results in systems which are wildly out of balance in the amount of processing or networking bandwidth required based on the actual computation that is required.
Accordingly, the inventor has determined that it would be desirable to be able to analyze the performance of an application executing on a parallel processing system. It would also be desirable to be able to estimate such performance based on assumed data set sizes and variations of the architecture of a parallel processing system. The present invention provides such abilities.
SUMMARY OF THE INVENTION
The invention provides a method by which the resources necessary to run an application or a set of applications on a parallel processing system can be effectively estimated, measured, and verified. The preferred embodiment creates a data file from a graph describing the application on the parallel processing system. Using that data file, plus the processing speeds of system components, the flow of data, and the size and counts of data records throughout the system, equations for the amount of time required for each component are determined.
These equations are then used to provide calculations of processing times on supplied data sets. This information preferably is displayed in spreadsheet form. Charts can be created by calculating times for multiple data sets. Future trends can be predicted by analyzing historical data and such analyses can be displayed in spreadsheets or charts as well.
For evaluation of actual systems, information about the components, such as processing speed, is updated as execution of the application is monitored. This allows measuring of current systems as well as verification of performance.
The details of the preferred embodiment of the invention are set forth in the accompanying drawings and the description below. Once the details of the invention are known, numerous additional innovations and changes will become obvious to one skilled in the art.


REFERENCES:
patent: 5475842 (1995-12-01), Gilbert et al.
patent: 5522022 (1996-05-01), Rao et al.
patent: 5742814 (1998-04-01), Balasa et al.
patent: 5806059 (1998-09-01), Tsuchida et al.
patent: 5935216 (1999-08-01), Benner et al.
IBM, Database 2 AIX/6000 Programming Reference manual, 1993, pp. 282-283.
Apers, Peter M.G., et al., “PRISM/DB: A Parallel, Main Memory Relational DBMS”, Dec. 1992, IEEE Transactions on Knowledge and Data Engineering, vol. 4, No. 6, pp. 541-554.
Boral, Haran, et al., “Prototyping Bubba, A Highly Parallel Database System”, Mar. 1990, IEEE Transactions on Knowledge and Data Engineering, vol. 2, No. 1, pp. 4-23.
DeWitt, David J., et al., “The Gamma Database Machine Project”, Mar. 1990, IEEE Transactions on Knowledge and Data Engineering, vol. 2, No. 1., pp. 44-62.
Frieder, Ophir and Chaitanya K. Baru, “Site and Query Scheduling Policies in Multicomputer Database Systems”, Aug. 1994, IEEE Transactions on Knowledge and Data Engineering, vol. 6, No. 4, pp. 609-619.
Graefe, Goetz, “Volcano—An Extensible and Parallel Query Evaluation System”, Feb. 1994, IEEE Transactions on Knowledge and Date Engineering, vol. 6, No. 1, pp. 120-135.
Graefe, Goetz and Diane L. Davison, “Encapsulation of Parallelism and Architecture-Independence in Extensible Database Query Execution”, Aug. 1993, IEEE Transactions on Software Engineering, vol. 19, No. 8, pp. 749-764.

Affiliated with

Also associated with

Rating

Method for analyzing capacity of parallel processing systems does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for analyzing capacity of parallel processing systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for analyzing capacity of parallel processing systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2537657