When a computer program is built, the code is typically written in a high level language, such as C++. The code is typically placed in one or more source files. Upon compiling, these source files may be made into object files, and combined with other object files to create the final software.
Make is a software tool that automates the procedures required to compile a program. The interdependencies between different source files may be stored in a makefile, which enables Make to recompile only those files that have been changed. A typical makefile may read as follows:
  x1.o:    cc -c x1.c  x2.o:  cc -c x2.ca.out: x1.o x2.o  1d -o a.out x1.o x2.o
This indicates that object file x1.o is made by compiling x1.c, x2.o is made by compiling x2.c, and a.out is made by linking x1.o and x2.o.
Make operates sequentially, as due to the dependencies certain actions must be done before other actions. However, there are some situations where actions could be done simultaneously (if they are not dependent on one another). Make does not provide for any facility to take advantage of this fact. Distributed Make (Dmake) was therefore created to allow non-dependent actions to be executed in parallel, such as on different systems, to speed compile time.
The Dmake command includes a parameter indicating a maximum number of resources to utilize. This is often used because it is can be beneficial to leave resources for other people.
The problem with this maximum parameter is that it can often be set too high for optimal compiling. This occurs if, for example, the programmer overestimates the amount of resources available or unexpected jobs begin utilizing resources.
This problem may be illustrated through the use of several examples. In each of these examples, Dmake starts 64 parallel jobs, with each job taking 256 MB of memory and 60 seconds of CPU time. FIG. 1 is a graph illustrating an example of the build operation in a system having 64 CPUs and more than 16 GB of memory. This is a case where there are plenty of resources, and thus the program compiles quickly, in about 60 seconds.
FIG. 2 is a graph illustrating an example of the build operation in a system having 4 CPUs and more than 16 GB of memory. Here, there are a moderate amount of resources, and thus the program still compiles in a reasonable time, about 20 minutes, although not as fast as the example in FIG. 1.
FIG. 3 is a graph illustrating an example of the build operation in a system having 4 CPUs and less than 16 GB of memory. Here, the build will take a very long time because when the memory limit is exceeded, swapping must occur (indicated by area 300). The overall parallel system runs very inefficiently whenever swapping must occur.
Thus, the maximum parameter specified by the programmer may result in an oversubscription of the system, resulting in a less than ideal throughput. What is needed is a solution that achieves the optimum throughput on the system.
USPTO Backgrounds
USPTO Backgrounds