Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-10-30
2001-11-20
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C709S241000, C709S241000
Reexamination Certificate
active
06321373
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the control of resources in a parallel computing environment.
BACKGROUND OF THE INVENTION
When a program is executed on a multiple resource system, many resources may be used to execute the program to completion. Depending on the requirements of the program, different kinds of resources may be required to run the program to completion. For example, a program requires processing resources for executing the program and for manipulation of data; it also requires memory to store intermediate and final results; and it may require resources of a file system. A program may be constructed so that multiple resources of the same kind can be used in order to speed up the program execution or to handle larger problem sizes and/or larger data sets. The resources used by a program may be allocated at the beginning of program execution or may be allocated during the course of execution just prior to its use. For example, all memory used by a program during the course of execution might be allocated only once at the beginning of program execution or instead might be allocated during execution just prior to generation of data and then deallocated when no longer necessary. Resources may be requested by a program explicitly or implicitly. In an explicit allocation, the program makes a request for specific resources explicitly; for example, a program may request a certain amount of memory or may request a specific set of processors prior to scalable nature of these parallel environments. Because of these considerations, in a scalable multiprocessor environment, the resource boundaries cannot be fixed at the time applications are written or even at compile time. For example, the number of processors on which an application may be run cannot be fixed a priori, or it may not be desirable to do so in order to realize the flexibility associated with scalable architectures. Furthermore, it has been observed that the data input to an application can have a large impact on the performance of the computations since concurrency and data distribution are both affected by the particular problem being solved. See J. Saltz, H. Berryman, and J. Wu, Multiprocessing and Run-Time Compilation, “Concurrency: Practice and Experience”, vol. 3(6), pp. 573-592, December, 1991. In such cases, the actual resource requirements to solve a problem to completion can be known only after the inputs to the problem are defined and the utilization of these resources may be determined only during the course of the program execution. When multiprocessor systems are multiprogrammed, a new dimension is added to the scheduling problem as multiple parallel jobs compete dynamically for resources. In some research systems, as discussed in C. Polychronopoulos, “Multiprocessing versus Multiprogramming”, Proceedings of the 1989 International Conference on Parallel Processing, Aug. 8-12, 1989, pp. II-223-230; A. Gupta, A. Tucker, and L. Stevens, “Making Effective Use of Shared-Memory Multiprocessors: The Process Control Approach”, Technical Report CSL-TR-91-475A, Computer Systems Laboratory, Stanford University, 1991; and S. Leutenegger and M. Vernon, “Multiprogrammed Multiprocessor Scheduling Issues”, Research Report RC-17642, IBM Research Division, February 1992, resources are rearranged during the lifetime of a parallel job. In the presence of multiple applications, all vying for the same resources, some form of efficient dynamic scheduling of resources is essential.
The scalable nature of parallel environments requires that an application be able to adapt to a particular configuration of the underlying system whenever it is invoked to solve a particular problem. Not only should the program as a whole be able to reconfigure, but to achieve flexibility and efficiency, the components of a program should be reconfigurable with respect to one another. For example, for any specified level of resources, the program data structures may have to be distributed suitably and the bounds for loops executed by each processor may have to be adjusted accordingly.
In summary, parallel applications developed for scalable systems with multiple resources have the following important characteristics:
i. Dynamism: Resource requirements change dynamically during the course of computations.
ii. Reconfigurability: Each stage of computations can be designed to operate under multiple levels of resources.
iii. Shareability: Applications often are required to share data and physical resources.
Thus, any resource management system for controlling of the resources associated with a parallel environment must have the following characteristics:
i. Dynamism: It should be possible to acquire and release resources dynamically on demand.
ii. Reconfigurability: It should be possible to reconfigure the allocated resources to individual applications.
iii. Shareability: It should be possible to dynamically partition the resources both in space and time.
To realize these characteristics, it is necessary for the end users and for the system itself to monitor the resources allocated to each segment of computations in an application and to steer the program to maximize the respective performance goals. In view of the above, a run-time system is necessary to integrate the resource manager and the parallel application in an intelligent manner.
PROBLEMS WITH PRIOR ART
Current parallel systems provide very limited control over resources. Often, a program requests the maximum amount of resources at the beginning and the resources are kept throughout the lifetime of the program. Thus, the resources are under-utilized in less demanding segments of the program. Furthermore, current systems do not provide any interactive control over the resources. The extent of dynamism is limited to redistribution of data structures at run-time, such as in high performance Fortran (HPF) systems. In C. H. Koelbel, D. B. Loveman, R. S. Schreiber, G. L. Steele Jr., and M. E. Zosel, “The High Performance Fortran Handbook”, The MIT Press, Cambridge, MASS., 1994, there is no provision for meaningful dynamic acquisition or release of processor resources during the course of program execution. Examples of systems where parallel jobs are run on a fixed-size partition include the IBM SP2 (See Special Issue on IBM POWERParallel Systems, IBM Systems Journal, vol. 34, no. 2, 1995), the Cray T3D (See Cray Research Inc., “Cray T3D System Architecture Overview Manual”, Eagan, Minn., 1994), and the Thinking Machines CM-5 (See Thinking Machines Corp., “The Connection Machine CM-5 Technical Summary”, Cambridge, Mass., 1992). MPI allows dynamic acquisition and release of processors, but there is no redistribution of control or data structures. See Message Passing Interface Forum, “MPI: A Message-Passing Interface Standard”, May, 1994.
We elaborate the above points in the following.
Existing art allows limited manipulation (i.e., allocation/deallocation and scheduling) of processors and memory to parallel applications. For example, prior to beginning the execution of a parallel application on a multiprocessor system, a user can ask for a specific number of processors or ask for processors that fall within a range. However, during the course of execution, processors cannot be explicitly allocated and deallocated in a manner similar to the way memory can be allocated and deallocated in a uniprocessor environment. In a pure shared memory environment, using the process fork mechanism, one can create processes dynamically during the course of execution, which in turn can be served by a pool of processors. Thus, under such an environment, services of additional processors may be obtained implicitly. Similarly, threads can be created dynamically to make use of a variable number of processing elements. However, in both cases, compile-time and run-time optimizations (such as minimization of memory accesses by cache, and register reuse) cannot be fully performed because of the dynamic data-sharing introduced in these models. Examples of research in dynamic control of processors for shared-
Ekanadham Kattamuri
Moreira Jose Eduardo
Naik Vijay Krishnarao
Chaki Kakali
Dougherty Anne Vachon
Ellenbogen Wayne L.
International Business Machines - Corporation
LandOfFree
Method for resource control in parallel environments using... 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 resource control in parallel environments using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for resource control in parallel environments using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2615066