Information processing apparatus, parallel computing system, job schedule setting program, and job schedule setting method

The present invention relates to an information processing apparatus, a parallel computer system, a job schedule setting program, and a job schedule setting method.

A system that executes processing using multiple compute nodes in parallel is used. In the system, software called a scheduler executed by the management node may assign processing to each computing node. For example, there is a proposal that the backfill scheduler places jobs from high-priority jobs in the queue to unused space on the scheduler map and executes scheduled jobs over time. There is also a proposal to improve the system utilization rate by using the backfill scheduler to advance the execution of small jobs within the range that does not delay the start of execution of large jobs that make heavy use of computational resources.

In addition, two schedules are created, one for allowing the suspension of the job being executed by one of the multiple computational resources and the other for not allowing it, and by comparing the value indicating the profit and the value indicating the loss of both schedules. There are also suggestions for determining an appropriate schedule.

In a method of solving a combination problem such as a traveling salesman problem or job shop scheduling, there is a proposal to search for a better solution by a process called reordering for a solution found by a priority algorithm.

<p num="0005"><patcit num="1"><text>Japanese Unexamined Patent Publication No. 2012-215933</text></patcit><patcit num="2"><text>Japanese Unexamined Patent Publication No. 2012-173753</text></patcit><patcit num="3"><text>Japanese Unexamined Patent Publication No. 2013-41529</text></patcit><patcit num="4"><text>International Publication No. 2012/020474</text></patcit><patcit num="5"><text>Japanese Patent Application Laid-Open No. 2005-56421</text></patcit></p>

<p num="0006"> As described above, it is conceivable to execute each of the prioritized jobs sequentially according to the priority at the earliest time when the jobs can be executed. However, in this method, the free time of computational resources is only allocated to subsequent jobs in order of priority. For this reason, the free time of computational resources is easily divided into small pieces, and when the scheduling results of a plurality of jobs are viewed, the computational resources are not always efficiently allocated to each job. There is. For example, it may take a long time to complete all jobs.</p><p num="0007"> In one aspect, it is an object of the present invention to provide an information processing apparatus, a parallel computer system, a job schedule setting program, and a job schedule setting method that can streamline job execution.</p>

<p num="0008"> In one aspect, an information processing device is provided. This information processing device has a storage unit and a calculation unit. The storage unit stores information on available time zones of a plurality of computing nodes. Based on the information, the calculation unit finds the first time in which the highest priority job can be executed among a plurality of jobs, and is a candidate for the execution start time of the highest priority job later than the first time. If there is a second time that can run more jobs within a given time range than running the highest priority job from time 1, run the highest priority job and other jobs from the second time. Assign multiple jobs to multiple compute nodes.</p><p num="0009"> Further, in one aspect, a parallel computer system having a plurality of computing nodes and a management node is provided. Multiple compute nodes can be assigned multiple jobs. The management node finds the first time in which the highest priority job among multiple jobs can be executed based on the information of the available time zone of multiple compute nodes, and the highest priority is later than the first time. If there is a second time that is a candidate for the job execution start time and can execute more jobs within a predetermined time range than executing the highest priority job from the first time, the highest priority is given from the second time. Assign multiple jobs to multiple compute nodes to run one job and another.</p><p num="0010"> Also, in one aspect, a job schedule setting program is provided. This job schedule setting program asks the computer for the first time in which the highest priority job among multiple jobs can be executed based on the information on the available time zones of multiple compute nodes, and the first time. If there is a second time that is a candidate for the execution start time of the later highest priority job and can execute more jobs within a predetermined time range than executing the highest priority job from the first time, the first Assign multiple jobs to multiple compute nodes so that the highest priority job and other jobs are executed from the time of 2, and execute the process.</p><p num="0011"> Also, in one aspect, a job schedule setting method is provided. In this job schedule setting method, the computer finds the first time in which the highest priority job among a plurality of jobs can be executed based on the information of the available time zone of a plurality of compute nodes, and the first time is obtained. If there is a second time that is a candidate for the execution start time of the later highest priority job and can execute more jobs within a predetermined time range than executing the highest priority job from the first time, the first Assign multiple jobs to multiple compute nodes to run the highest priority job and other jobs from time 2.</p>

<p num="0012"> On one side, you can streamline job execution.</p>

<figref num="1">It is a figure which shows the information processing apparatus of 1st Embodiment.</figref><figref num="2">It is a figure which shows the parallel computer system of the 2nd Embodiment.</figref><figref num="3">It is a figure which shows the hardware example of the management node.</figref><figref num="4">It is a figure which shows the functional example of the management node.</figref><figref num="5">It is a figure which shows the example of the time map.</figref><figref num="6">It is a figure which shows the example of the priority of the job waiting for allocation.</figref><figref num="7">It is a figure which shows the example of the job information waiting for allocation.</figref><figref num="8">It is a figure which shows the example of the structure which manages the allocation target job.</figref><figref num="9">It is a figure which shows the management example of the allocation target job according to a priority.</figref><figref num="10">It is a figure which shows the example of the structure which manages available resources.</figref><figref num="11">It is a figure which shows the management example of the available resource for every time.</figref><figref num="12">It is a figure which shows the management example of the available resource with respect to time t1.</figref><figref num="13">It is a figure which shows the management example of the job assigned at time t1.</figref><figref num="14">It is a figure which shows the example of the structure which manages a temporary allocation.</figref><figref num="15">It is a figure which shows the example of the temporary allocation of a job starting from time t1.</figref><figref num="16">It is a figure which shows the management example of a plurality of tentatively assigned jobs.</figref><figref num="17">It is a figure which shows the example of the job information waiting for execution.</figref><figref num="18">It is a figure which shows the example of the parameter information.</figref><figref num="19">It is a figure which shows the example of the data flow of a management node.</figref><figref num="20">It is a figure which shows the processing example of the management node.</figref><figref num="21">It is a flowchart which shows the example of allocation candidate time detection.</figref><figref num="22">It is a flowchart which shows the example of temporary resource allocation.</figref><figref num="23">It is a flowchart which shows the selection example of the temporary allocation target job.</figref><figref num="24">It is a flowchart which shows the arrangement example of the temporary allocation target job.</figref><figref num="25">It is a flowchart which shows the example of allocation resource selection.</figref><figref num="26">It is a figure which shows the specific example of available resource information and job information.</figref><figref num="27">It is a figure which shows the detection example of the allocation candidate time.</figref><figref num="28">It is a figure which shows the example of the time of the upper limit of the allocation candidate time.</figref><figref num="29">It is a figure which shows the selection example of the temporary allocation target job.</figref><figref num="30">It is a figure which shows the selection example (continuation) of the temporary allocation target job.</figref><figref num="31">It is a figure which shows the example of the provisional allocation.</figref><figref num="32">It is a figure which shows the example (continuation) of a temporary allocation.</figref><figref num="33">It is a figure which shows the example of the available resource information after the update.</figref><figref num="34">It is a figure which shows the example of the temporary allocation pattern.</figref><figref num="35">It is a figure which shows the example (pattern Pt1) of the temporary allocation information.</figref><figref num="36">It is a figure which shows the example (pattern Pt2) of the temporary allocation information.</figref>

Hereinafter, the present embodiment will be described with reference to the drawings. [First Embodiment] FIG. 1 is a diagram showing an information processing apparatus according to the first embodiment. The information processing device 1 is connected to a plurality of computing nodes via a network. Multiple compute nodes include compute nodes 2,3,4. The information processing device 1 uses a plurality of computing nodes to execute a plurality of jobs in parallel. A job is a unit of processing assigned to each calculation node by the information processing apparatus 1. Another information processing device connected to the network may send a job execution request to the information processing device 1.

The information processing apparatus 1 assigns a priority to each job and manages it. Generally, a job with a relatively high priority starts execution earlier than a job with a relatively low priority. The job priority can be determined according to, for example, the order of arrival of the job execution requests, the priority of the group to which the user belongs or the user, the importance of the application that issued the job execution request, and the like. The information processing device 1 allocates a plurality of jobs to a plurality of calculation nodes according to the priority. The information processing device 1 may allocate the processing of one job across a plurality of calculation nodes, and each calculation node may execute the job in parallel. Each of the compute nodes executes the job assigned to it. The information processing device 1 may be called a "computer".

Here, the information processing apparatus 1 identifies each of the plurality of calculation nodes by the calculation node ID (IDentifier). The calculation node ID is identification information for each of the plurality of calculation nodes. For example, the information processing apparatus 1 identifies 12 calculation nodes by the calculation node IDs 0 to 11.

The information processing device 1 has a storage unit 1a and a calculation unit 1b. The storage unit 1a may be a volatile storage device such as RAM (Random Access Memory) or a non-volatile storage device such as an HDD (Hard Disk Drive). The arithmetic unit 1b is, for example, a processor. The processor may be a CPU (Central Processing Unit) or a DSP (Digital Signal Processor), or may include an integrated circuit such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array). The processor, for example, executes a program stored in RAM. Further, the "processor" may be a set of two or more processors (multiprocessor).

The storage unit 1a stores the first information indicating the available time zone of the plurality of computing nodes. The first information can also be said to be information indicating a time zone in which none of the jobs is assigned among the available times of each of the plurality of compute nodes. In the example of the first embodiment, jobs J1, J2, J3, J4, J5, J6, J7 have already been scheduled for a plurality of nodes including the compute nodes 2, 3, and 4 (FIG. 1). Equivalent to a time map). Of the plurality of compute nodes, the time zone that is not assigned to any job is the available time zone of the corresponding compute node.

The storage unit 1a stores a second piece of information indicating the required amount of the calculation node for each of the plurality of jobs. The required amount of compute nodes may include, for example, the number of compute nodes used to execute the job and the utilization time. For example, a computing node may be considered as one computer (information processing device or computer). When a computer includes a plurality of processors, the processor group (and the memory used by the processor group), which is a job allocation unit, may be considered as one calculation node among the plurality of processors. Alternatively, when the processor includes a plurality of cores, the core group (and the memory used by the core group), which is a job allocation unit, may be considered as one calculation node among the plurality of cores.

For example, the second information includes the required amount of compute nodes used to execute each of the jobs Ja, Jb, Jc, Jd. Jobs Ja, Jb, Jc, and Jd are unallocated (unscheduled) jobs for a plurality of compute nodes, and are the jobs to be allocated (scheduled) this time.

Priority is given to each of jobs Ja, Jb, Jc, and Jd. Job Ja has the highest priority. The priority of job Jb is lower than the priority of job Ja and higher than the priority of job Jc. The priority of job Jc is lower than that of job Jb and higher than that of job Jd. Job Jd has the lowest priority.

Based on the first and second information stored in the storage unit 1a, the calculation unit 1b obtains the first time during which the highest priority job among the plurality of jobs can be executed. It can be said that the first time is one of the candidate times for starting the execution of the highest priority job. For example, the arithmetic unit 1b obtains the time t1 as the first time in which the highest priority job Ja can be executed among the jobs Ja, Jb, Jc, and Jd. The arithmetic unit 1b attempts tentative scheduling according to the priority of jobs Ja, Jb, Jc, and Jd when job Ja is started from time t1. In this case, the higher priority job is scheduled not to run after the lower priority job (the higher priority job and the lower priority job are scheduled to start running at the same time). There are times). As a result, the arithmetic unit 1b obtains the scheduling candidate pattern P1.

Based on the first and second information, the calculation unit 1b is a candidate for the execution start time of the highest priority job later than the first time, and is determined rather than executing the highest priority job from the first time. Determine if there is a second time within the time range that allows many jobs to run. The information in the predetermined time range is, for example, the period T starting from the first time, and is stored in advance in the storage unit 1a.

For example, the arithmetic unit 1b prioritizes jobs Ja, Jb, Jc, and Jd when the execution start time of job Ja is set to time t2 (second time) later than time t1 (first time). Try tentative scheduling according to. As a result, the arithmetic unit 1b obtains the scheduling candidate pattern P2. For example, the calculation unit 1b determines that the number of job executions in the period T is larger in the pattern P2 than in the pattern P1 by comparing the patterns P1 and P2. Therefore, by setting the execution start time of job Ja to time t2, which is later than time t1, the arithmetic unit 1b has many more within a predetermined time range (for example, period T) than the job Ja is executed at time t1. Judge that the job can be executed.

Specifically, in pattern P1, the execution of job Jd is not completed within the period T, so the number of jobs that can be completed within the period T is three, jobs Ja, Jb, and Jc. On the other hand, in pattern P2, the execution of four jobs, jobs Ja, Jb, Jc, and Jd, can be completed within the period T. Therefore, it is possible to execute more jobs within the period T by starting the execution of the job Ja at the time t2 than by starting the execution of the job Ja at the time t1.

In this case, the calculation unit 1b delays the execution start time of the highest priority job from the first time, and causes the plurality of calculation nodes to execute the highest priority job and other jobs from the second time. Assign multiple jobs. For example, the calculation unit 1b delays the execution start time of job Ja from time t1 to time t2. That is, the arithmetic unit 1b adopts the scheduling result of the pattern P2 and sends jobs Ja, Jb, Jc to a plurality of calculation nodes so that the highest priority job Ja and other jobs Jb, Jc, Jd are started to be executed at time t2. , Jd is assigned.

As a result, job execution can be made more efficient. For example, a method of sequentially executing each prioritized job at the earliest time when the prioritized jobs can be executed can be considered. However, simply allocating jobs at the earliest time according to priority does not necessarily mean that computational resources are efficiently allocated to each job. It may take longer to complete all jobs. For example, as illustrated in pattern P1, execution of some of a plurality of jobs may not be completed within the period T. On the other hand, as illustrated in pattern P2, by delaying the execution start time of the highest priority job Ja from time t1 to time t2, the execution of the plurality of jobs may be completed within the period T.

Therefore, the information processing apparatus 1 also considers subsequent jobs Jb, Jc, and Jd when scheduling job Ja. Specifically, the information processing apparatus 1 acquires a plurality of patterns that are candidates for scheduling of jobs Ja, Jb, Jc, and Jd, and by comparing the plurality of patterns, a pattern capable of executing more jobs within the period T. Is adopted. The information processing device 1 allocates jobs to each calculation node according to the adopted pattern. For example, in pattern P2, the time until all the executions of jobs Ja, Jb, Jc, and Jd are completed can be made earlier than in pattern P1. In addition, pattern P2 can reduce the free time of the compute node compared to pattern P1, and can improve job throughput while maintaining job priority. In this way, job execution can be streamlined.

[Second Embodiment] FIG. 2 is a diagram showing a parallel computer system according to the second embodiment. The parallel computer system of the second embodiment includes a management node 100 and a plurality of computer nodes. Multiple compute nodes include compute nodes 200,300,400. Management node 100 and a plurality of compute nodes are connected to network 10. The network 10 is, for example, a LAN (Local Area Network).

Management node 100 allocates a plurality of jobs to a plurality of compute nodes. The management node 100 may receive a job execution request from another information processing device (not shown) via the network 10. The management node 100 is an example of the information processing device 1 of the first embodiment.

Compute nodes 200,300,400 execute the jobs assigned by management node 100. In the example of the second embodiment, each of the compute nodes 200, 300, 400 is one computer (as well as the other compute nodes). Computational nodes 200,300,400 are examples of compute nodes 2,3,4 of the first embodiment.

In the parallel computer system of the second embodiment, the management node 100 can execute a plurality of jobs in parallel by assigning a plurality of jobs to a plurality of computer nodes. In the example of the parallel computer system of the second embodiment, the computer node to which the execution of a certain job is assigned in a certain time zone is dedicated to execute the corresponding job in the corresponding time zone. The required amount of computational resources allocated to a job can be expressed by "the number of computing nodes x the occupied time" (the required amount of computational resources can also be called the required amount of computational nodes).

As described above, a system that realizes high-speed processing by processing a plurality of jobs in parallel by a plurality of computing nodes may be called an HPC (High Performance Computing) system.

FIG. 3 is a diagram showing a hardware example of the management node. The management node 100 includes CPU 101, 102, RAM 103, HDD 104, image signal processing unit 105, input signal processing unit 106, media reader 107, and communication interface 108. These hardware units are connected to the bus within management node 100. The CPUs 101 and 102 are examples of the arithmetic unit 1b of the first embodiment, and the RAM 103 or HDD 104 is an example of the storage unit 1a of the first embodiment.

CPUs 101 and 102 are processors containing one or more cores that execute program instructions. For example, CPU 101 has a plurality of cores including cores 101a and 101b. Multiple cores belonging to the same or different CPUs can execute instructions in parallel with each other. The CPUs 101 and 102 load at least a part of the programs and data stored in the HDD 104 into the RAM 103 and execute the programs. In addition, each core may be called a "processor", and a set of a plurality of processors may be called a "processor" (multiprocessor).

RAM103 is a volatile memory that temporarily stores programs executed by CPUs 101 and 102 and data used by CPUs 101 and 102 for calculations. The management node 100 may include a type of memory other than RAM, or may include a plurality of memories.

The HDD 104 is a non-volatile storage device that stores software programs such as an OS (Operating System) and application software, and data. The management node 100 may be provided with other types of storage devices such as a flash memory and an SSD (Solid State Drive), and may be provided with a plurality of non-volatile storage devices.

The image signal processing unit 105 outputs an image to the display 11 connected to the management node 100 in accordance with the instructions from the CPUs 101 and 102. As the display 11, a CRT (Cathode Ray Tube) display, a liquid crystal display (LCD: Liquid Crystal Display), a plasma display (PDP: Plasma Display Panel), an organic EL (OEL: Organic Electro-Luminescence) display, or the like can be used. ..

The input signal processing unit 106 acquires an input signal from the input device 12 connected to the management node 100 and outputs it to at least one CPU. As the input device 12, a mouse, a touch panel, a pointing device such as a touch pad or a trackball, a keyboard, a remote controller, a button switch, or the like can be used. Further, a plurality of types of input devices may be connected to the management node 100.

The medium reader 107 is a reading device that reads programs and data recorded on the recording medium 13. As the recording medium 13, for example, a magnetic disk such as a flexible disk (FD) or HDD, an optical disk such as a CD (Compact Disc) or a DVD (Digital Versatile Disc), a magneto-optical disk (MO), A semiconductor memory or the like can be used. The medium reader 107 stores, for example, a program or data read from the recording medium 13 in the RAM 103 or the HDD 104.

The communication interface 108 is an interface that is connected to the network 10 and communicates with other information processing devices including a plurality of computing nodes via the network 10. The communication interface 108 may be a wired communication interface connected to a communication device such as a switch by a cable, or a wireless communication interface connected to a base station or the like by a wireless link.

The number of CPUs included in the management node 100 may be one. Further, the management node 100 does not have to include the media reader 107. Further, the management node 100 does not have to include the image signal processing unit 105 and the input signal processing unit 106 when controlled from the terminal device operated by the user via the network 10. Further, the management node 100 does not have to include the communication interface 108. Further, the display 11 and the input device 12 may be formed integrally with the housing of the management node 100. Further, each calculation node including the calculation nodes 200, 300, 400 can be realized by using the same unit as the management node 100. Like the management node 100, each calculation node may not include at least one of the image signal processing unit 105, the input signal processing unit 106, and the medium reader 107.

FIG. 4 is a diagram showing a functional example of the management node. The management node 100 has a job storage unit 110 waiting to be allocated, a job storage unit 120 to be allocated, a resource information storage unit 130, a job storage unit 140 waiting to be executed, a parameter storage unit 150, a job reception unit 160, a job selection unit 170, and a resource selection unit. It has 180 and a job execution instruction unit 190.

The allocation-waiting job storage unit 110, the allocation target job storage unit 120, the resource information storage unit 130, the execution-waiting job storage unit 140, and the parameter storage unit 150 are realized as storage areas secured in the RAM 103 and the HDD 104. The job reception unit 160, the job selection unit 170, the resource selection unit 180, and the job execution instruction unit 190 are realized by the CPUs 101 and 102 executing the programs stored in the RAM 103. Software having the functions of the job reception unit 160, the job selection unit 170, the resource selection unit 180, and the job execution instruction unit 190 may be called a "job scheduler".

The job storage unit 110 waiting for allocation stores information (job information waiting for allocation) of jobs for which resources have not been allocated among the submitted jobs. In the following description, a job for which resources have not been allocated among the submitted jobs may be referred to as a waiting for allocation job. The information of the job waiting to be allocated includes the required amount of computational resources (number of computing nodes × occupied time) for executing the job. In addition, the job information waiting to be assigned may include information used for determining the priority described later (arrival time for each job, information on the issuing application and the user who uses the application, and the like).

The allocation target job storage unit 120 stores the information of the job to be allocated the computational resources this time. The information stored in the allocation target job storage unit 120 includes allocation target job information and subsequent target job information.

The job information to be assigned includes information indicating the job having the highest scheduling priority among the jobs waiting to be assigned. Here, the job having the highest scheduling priority among the jobs waiting for allocation may be referred to as "assignment target job".

The successor target job information includes information indicating the job to be evaluated for temporary allocation together with the allocation target job. Here, a job to be evaluated for provisional allocation together with an allocation target job may be referred to as a subsequent target job.

Further, "temporary allocation" indicates that the allocation target job and the subsequent target job are tentatively allocated (so as not to affect the actual scheduling) from a certain allocation candidate time to the temporary allocation end time. The assignment candidate time indicates the time at which provisional allocation is performed among the times during which the assignment target job can be assigned. "Temporary allocation end time" indicates the end time when performing temporary allocation.

The resource information storage unit 130 stores information on computational resources (available resource information) that can be used to execute a job. Computational resource information is information that indicates how much time is available for job execution at a computational node at a given time.

The execution-waiting job storage unit 140 stores the information of the job (waiting-for-execution job information) that has been allocated the computational resources of the compute node (it can be said that it has been scheduled) and is waiting to be executed by the compute node. In the following description, a job waiting for the time by the calculation node may be referred to as a "waiting job". The resource selection unit 180 selects the computational resources to be assigned to the job waiting to be executed.

The parameter storage unit 150 stores parameter information used for processing of the job selection unit 170 and the resource selection unit 180. For example, the parameter information includes information that serves as a reference for selecting a succeeding target job and information that serves as a reference for selecting computational resources.

The job reception unit 160 receives a job execution request. The job reception unit 160 stores the allocation-waiting job information according to the received job in the allocation-waiting job storage unit 110. The job execution request may be issued by an application running on the management node 100, or may be issued by an information processing device different from the management node 100 and the calculation nodes 200,300,400.

The job selection unit 170 sorts the assignment-waiting jobs according to a predetermined priority based on the allocation-waiting job information stored in the allocation-waiting job storage unit 110. The job selection unit 170 determines the job priority according to, for example, the arrival order of job execution requests, the priority of the group to which the user belongs, the priority of the user, the importance of the application that issued the job execution request, and the like. Here, the job selection unit 170 has an allocation target job selection unit 171 and a subsequent target job selection unit 172.

The allocation target job selection unit 171 generates allocation target job information based on the allocation target job information stored in the allocation target job storage unit 110 and stores it in the allocation target job storage unit 120. The allocation target job information includes information indicating the first job (allocation target job) and the last job among the plurality of jobs to be allocated the computational resources this time. The first job (assignment target job) is the job with the highest priority among the plurality of jobs. The terminating job is the job with the lowest priority among the plurality of jobs.

The succeeding target job selection unit 172 generates the succeeding target job information based on the allocation waiting job information stored in the allocation target job storage unit 110, and stores it in the allocation target job storage unit 120. The successor target job selection unit 172 selects the successor target job in the order of job priority. For example, if the number of jobs waiting to be assigned increases, it may take time to evaluate the succeeding target job. Therefore, for example, in the parameter information, the upper limit of the number of jobs to be evaluated for temporary allocation is set in advance. The succeeding target job selection unit 172 selects the succeeding target job until the upper limit is reached. In addition to that, in the parameter information, a limit value of the number of jobs to be allocated according to the free space of computational resources in the system may be specified in advance. Alternatively, the upper limit of the number of subsequent target jobs may be set to the total number of jobs waiting to be allocated stored in the job storage unit 110 waiting to be allocated.

As described above, the management node 100 specifies the first job and the last job by the allocation target job information, and based on the subsequent target job information, a series of jobs from the first job to the last job. Can be identified as the job to be evaluated for assignment.

The resource selection unit 180 allocates computational resources to the allocation target job and the succession target job based on the allocation target job information and the succession target job information stored in the allocation target job storage unit 120. The resource selection unit 180 includes an allocation candidate time detection unit 181, a temporary resource allocation unit 182, and an allocation resource selection unit 183.

The allocation candidate time detection unit 181 identifies the allocation target job based on the allocation target job information stored in the allocation target job storage unit 120. The allocation candidate time detection unit 181 is a candidate for the starting time (which allocates computational resources to the job to be allocated, based on the resource information stored in the resource information storage unit 130 and the parameter information stored in the parameter storage unit 150. Detect multiple allocation candidate times).

The temporary resource allocation unit 182 temporarily allocates computational resources to the allocation target job and the subsequent target job, starting from each of the plurality of allocation candidate times detected by the allocation candidate time detection unit 181. For example, the temporary resource allocation unit 182 pays attention to the first allocation candidate time, and attempts to allocate the allocation target job and the subsequent allocation target job on the time map starting from the first allocation candidate time. Further, the temporary resource allocation unit 182 pays attention to the second allocation candidate time, and tries to arrange the allocation target job and the subsequent allocation target job on the time map starting from the second allocation candidate time. Job priority is taken into consideration in job placement. As a result, the temporary resource allocation unit 182 obtains a plurality of candidates for the calculation resource allocation pattern for the allocation target job and the subsequent target job. The candidate for the allocation pattern may be referred to as a temporary allocation pattern. The temporary resource allocation unit 182 stores information of a plurality of temporary allocation patterns in the resource information storage unit 130.

The allocation resource selection unit 183 selects the provisional allocation pattern of the computational resources to be adopted for the allocation target job and the subsequent target job based on the information of the plurality of temporary allocation patterns stored in the resource information storage unit 130. The selection criterion is registered in advance in the parameter information stored in the parameter storage unit 150, for example. For example, parameter information can be used as criteria for selecting a temporary allocation pattern: (1) a large number of jobs can be executed during a predetermined period, (2) each job is executed quickly, and (3) during a predetermined period. It may contain information indicating conditions such as a small amount of free computational resources in. The predetermined period is a predetermined time range, and may be a fixed period after the time starting from the earliest time in which the highest priority job can be executed, or a fixed period after the current time starting from the current time. It may be a period. Each condition has a relative weight to the other conditions. The higher the weight condition, the higher the priority of pattern selection. The allocation resource selection unit 183 generates execution-waiting job information based on the selected temporary allocation pattern, and stores it in the execution-waiting job storage unit 140.

The job execution instruction unit 190 instructs the execution of a job for each of a plurality of calculation nodes based on the execution-waiting job information stored in the execution-waiting job storage unit 140. FIG. 5 is a diagram showing an example of a time map. Figure 5 shows the state in which execution of seven jobs J1, J2, J3, J4, J5, J6, and J7 is assigned to 12 compute nodes. Computational nodes are identified by Computational Node ID. For example, the calculation node IDs "0" to "11" are assigned to the 12 calculation nodes. Information showing the schedule contents as shown in FIG. 5 is sometimes called a time map. In FIG. 5, the times t0 to t5 at which any job starts or completes are also illustrated.

According to the example of FIG. 5, job J1 is assigned to the three calculation nodes indicated by the calculation node IDs 0 to 2 in the period from time t0 to t4. During the period from time t0 to t2, job J2 is assigned to one calculation node indicated by the calculation node ID 3. During the period from time t0 to t1, job J3 is assigned to the three calculation nodes indicated by the calculation node IDs 4 to 6. During the period from time t0 to t2, job J4 is assigned to one calculation node indicated by the calculation node ID 7. During the period from time t0 to t3, job J5 is assigned to the four calculation nodes indicated by the calculation node IDs 8 to 11. During the period from time t3 to t5, job J6 is assigned to the six calculation nodes indicated by the calculation node IDs 6 to 11. At times t4 to t5, job J7 is assigned to the four calculation nodes indicated by the calculation node IDs 0 to 3. For the above 12 calculation nodes, the available resource R1 is a calculation resource other than the calculation resources already allocated to jobs J1, J2, J3, J4, J5, J6, and J7 after time t0. The available resource R1 can be allocated for a new job.

FIG. 6 is a diagram showing an example of the priority of jobs waiting to be assigned. Jobs are identified by job ID. In the following description, a job whose job ID is "A" may be referred to as "Job A".

For example, jobs waiting to be assigned include jobs A, B, C, D, ... The allocation target job selection unit 171 refers to the allocation waiting job storage unit 110, and selects, for example, job A as the allocation target job. The successor target job selection unit 172 selects jobs B, C, and D as successor target jobs. When selecting jobs to be assigned, the priority (scheduling priority) of each job is taken into consideration. That is, the allocation target job selection unit 171 selects the allocation target jobs in descending order of priority of the assignment waiting jobs. The first job is job A. The final job is job D. In this case, the allocation target job selection unit 171 recognizes the terminal job as job D. The number of jobs to be selected as the job to be assigned is preset in the parameter storage unit 150 as parameter information as described above (for example, it is preset to select four jobs).

FIG. 7 is a diagram showing an example of job information waiting to be assigned. The allocation-waiting job information 111 is stored in the allocation-waiting job storage unit 110. The job information 111 waiting for allocation includes items of job ID, requested resource amount, and resource usage time.

Job identification information (job ID) is registered in the job ID item. In the item of required resource amount, the number of calculation nodes requested to execute the corresponding job is registered. In the resource usage time item, the usage time of each compute node requested to execute the corresponding job is registered.

For example, in the allocation waiting job information 111, information that the job ID is A, the required resource amount is 2, and the resource usage time is tA is registered. This indicates that job A waiting for allocation is a job that is executed exclusively for two compute nodes and time tA. In this case, the computational resource requirement for job A is 2 × tA.

Information on the requested resource amount and the resource usage time is similarly registered in the allocation waiting job information 111 for other jobs. Job B is a job that is executed exclusively for one compute node and time tB. Job C is a job that is executed exclusively for one compute node and time tC. Job D is a job that is executed exclusively for one compute node and time tD.

The job information 111 waiting to be assigned may include information used for determining the priority. The information used for determining the priority includes, for example, the arrival time of the job execution request, the software that issued the job execution request, the user who uses the software (or the group to which the user belongs), and the like. obtain. Alternatively, each record of job information 111 waiting to be assigned may be sorted in order of priority.

FIG. 8 is a diagram showing an example of a structure that manages the jobs to be assigned. The allocation target job information and the succession target job information are used for managing the allocation target job and the succession target job. The allocation target job information and the subsequent target job information are stored in the allocation target job storage unit 120. FIG. 8 shows an example of the allocation target job information structure 121 (schedjobinfo) and the subsequent target job information structure 122 (jobinfo).

Structure 121 is an example of a structure of job information to be assigned. Structure 121 includes the number of job information (num_jobs), a pointer to the first job information (jobinfo * head_p), and a pointer to the end job information (jobinfo * tail_p). The number of job information is the number of subsequent target job information indicated by the allocation target job information (the number of the first job, the end job, and the number of jobs between the first job and the end job). The pointer to the first job information indicates the storage address on the RAM 103 of the succeeding target job information corresponding to the first job. The pointer to the end job information indicates the storage address of the succeeding target job information corresponding to the end job on RAM103. The specific data stored on the RAM 103 using the structure 121 can be called an instance of the structure 121 (the same applies to other structures). The job information to be assigned is one instance of structure 121.

Structure 122 is an example of a structure of subsequent target job information. The structure 122 contains information on a pointer to the next job information (jobinfo * next_p), a job ID (jid), a requested resource amount (num_reqnids), and a resource usage time (timespec reqtime). The pointer to the next job information indicates the storage address of the next succeeding job information on RAM103. The information of the job ID, the requested resource amount, and the resource usage time is the information corresponding to the item of the same name in the allocation waiting job information 111 illustrated in FIG. 7. The job information to be assigned is one instance of structure 122. Subsequent target job information can be created for each job using the structure 122.

FIG. 9 is a diagram showing an example of managing assigned jobs according to priority. The allocation target job and the succession target job are managed according to the priority of each job by the allocation target job information and the succession target job information.

Specifically, the succeeding target job information indicated by the pointer to the head job (head_p) is the information of the head job (assignment target job). On the other hand, the succeeding target job information indicated by the pointer to the terminal job (tail_p) is the information of the terminal job. The end job has the lowest priority among the assigned jobs and the succeeding jobs. Then, the pointer (next_p) to the next job information indicates the job information of the job having the next lowest priority after the own job. With such a data structure, the management node 100 manages the order of jobs from the first job to the last job in descending order of priority.

FIG. 10 is a diagram showing an example of a structure that manages available resources. For the management of available resources, available resource management information, available resource information, resource information, temporary allocation work information, and temporary allocation job information are used. The available resource management information, available resource information, resource information, temporary allocation work information, and temporary allocation job information are stored in the resource information storage unit 130. In FIG. 10, the available resource management information structure 131 (availrschead), the available resource information structure 132 (availrsc), the resource information structure 133 (availrscinfo), and the temporary allocation work information structure 134 (allocrscinfo). And an example of the temporary allocation job information structure 135 (allocrscjobinfo) is shown.

Structure 131 is an example of a structure of available resource management information. Structure 131 contains a pointer (availrsc * head_p) to the first available resource information. The available resource management information is an instance of structure 131.

Structure 132 is an example of a structure of available resource information. The structure 132 is a pointer to the next element (available resource information) (availrsc * next_p), the time of available resources (timespec time), the number of resource information (num_rsc), and a pointer to the first resource information (availrscinfo). * arihead_p) and a pointer to the terminating resource information (availrscinfo * aritail_p).

The time of available resources is the start time of the free period of computational resources. In the available resource information, information (resource information) of one or more computational resources that can be used from the start time is managed. The number of resource information is the number of resource information managed by the available resource information. The pointer to the first resource information indicates the storage address of the first resource information on RAM103. The pointer to the terminating resource information indicates the storage address of the terminating resource information on RAM103. The available resource information is one instance of structure 132. The available resource information can be created for each available resource time using the structure 132.

Structure 133 is an example of a structure of resource information. Structure 133 includes a pointer to the next resource information (availrscinfo * next_p), a pointer to the previous resource information (availrscinfo * prev_p), the available time of computational resources (timespec availtime), the number of available nodes (num_nids), Contains a pointer to the available node ID (* nids_p) and a temporary allocation work area (allocrscinfo allocinfo).

The pointer to the next resource information indicates the storage address of the next resource information on RAM103. The pointer to the previous resource information indicates the storage address of the previous resource information on RAM103. The available time of the computational resource is the available time of the computational resource starting from the time included in the available resource information. One period in the time map can be specified by the time and the available time. The number of available nodes is the number of available compute nodes. The pointer to the available node ID indicates the storage address on RAM 103 where the list of compute node IDs of the available compute nodes is stored. The temporary allocation work area is information for work for temporarily allocating computational resources to a job. The resource information is one instance of structure 133. A plurality of resource information can be created by using the structure 133.

Structure 134 is an example of a structure of temporary allocation work information. Structure 134 includes the total number of temporary allocation nodes (total_alloc_nids), the number of temporary allocation job information (num_ajs), and a pointer to the first temporary allocation job information (allocrscjobinfo * aj_p).

The total number of temporary allocation nodes is the number of calculation nodes for which jobs have been provisionally allocated. The number of temporarily assigned job information is the number of information of the temporarily assigned job (that is, the job). The pointer to the first temporary allocation job information indicates the storage address of the first temporary allocation job information on RAM103. Temporary allocation work information is one instance of structure 134. A plurality of temporary allocation work information can be created by using the structure 134.

Structure 135 is an example of a structure of temporary allocation job information. Structure 135 contains a pointer to the next provisionally allocated job information (allocrscjobinfo * next_p), job ID (jid), and number of resources acquired (num_alloc_nids). The pointer to the next temporary allocation job information indicates the storage address of the next temporary allocation information on RAM103. The job ID is the job ID of the temporarily assigned job. The number of acquired resources is the number of compute nodes acquired (assigned to the job) by the job indicated by the job ID. Temporary allocation job information is an instance of structure 135. A plurality of temporary allocation job information can be created by using the structure 135.

FIG. 11 is a diagram showing an example of management of available resources for each time. The available resources for each of the times t0, t1, t2, t3, t4, and t5 are managed by the available resource information. The available resource management information includes a pointer to the first available resource information. Here, each available resource information is concatenated by a pointer (availrsc * next_p) in the order of earliest time. At times t0 to t5, time t0 is the earliest time. Therefore, the available resource information at the beginning is the available resource information related to time t0.

After that, the pointer of the available resource information at time t0 indicates the available resource information at time t1. The pointer of the available resource information at time t1 indicates the available resource information at time t2 (the illustration of the available resource information after time t2 is omitted). The pointer of the available resource information at time t3 indicates the available resource information at time t4. The pointer of the available resource information at time t4 indicates the available resource information at time t5.

FIG. 12 is a diagram showing an example of management of available resources at time t1. At time t1, the available resources are divided into the following two. The first available resource is the time zone of t3-t1 (available time) after the time t1 of one compute node with the compute node ID 6. Here, the operation of t3-t1 with respect to the time is an operation of obtaining the time difference between the time t3 and the time t1 (the same applies to other times). That is, the calculation node ID 6 can be used from time t1 to time t3. The second available resource is the time zone (no upper limit) after the time t1 of the two compute nodes with the compute node ID 4,5 (in the figure, the available time in this case is the infinite symbol . ).

The available time corresponds to the avail time of structure 133. The number of available nodes corresponds to num_nids in structure 133. The available node ID corresponds to the information indicated by the pointer nids_p of structure 133. The above first available resource and the second available resource at time t1 are managed by two resource information. Each resource information is concatenated in ascending order of available time.

Specifically, in the available resource information at time t1, num_rsc is 2. The pointer arihead_p indicates the first resource information corresponding to the first available resource. The pointer aritail_p indicates the second resource information corresponding to the second available resource.

The first resource information includes the following information. The pointer next_p indicates the second resource information. The pointer prev_p is NULL because the previous resource information does not exist in the first resource information. availtime is t3-t1. num_nids is 1. The pointer nids_p indicates the node ID 6. allocinfo is a temporary allocation work area for the first available resource.

The second resource information includes the following information: The pointer next_p is NULL because the next resource information does not exist in the second resource information. The pointer prev_p indicates the first resource information. The avail time is (infinity). num_nids is 2. nids_p indicates node ID 4,5. allocinfo is a temporary allocation work area for the second available resource.

FIG. 13 is a diagram showing a management example of the job assigned at time t1. FIG. 13 illustrates temporary allocation work information when job J8 is assigned to start execution at time t1. Here, it is assumed that the required amount of computational resources for job J8 is three compute nodes and the utilization time t3-t1. In this case, job J8 can be executed using the available resources at time t1 described above. When the available resources at time t1 are provisionally allocated to job J8, the provisional allocation status of job J8 is managed by the first resource information and the second resource information illustrated in FIG.

Specifically, in the first resource information, the temporary allocation work area (temporary allocation work information) allocinfo includes the following information. total_alloc_nids is 1. num_ajs is 1. The pointer aj_p indicates the first temporary allocation job information for job J8.

The first provisional allocation job information includes the following information. The pointer next_p is NULL because there is only one temporarily assigned job (job J8 only). jid is the job ID of the temporarily assigned job J8 (in FIG. 13, this is referred to as the ID of the temporarily assigned job J8). num_alloc_nids is 1 (because the provisionally assigned compute node is one compute node with compute node ID 6).

Further, in the second resource information, the temporary allocation work area (temporary allocation work information) allocinfo includes the following information. total_alloc_nids is 2. num_ajs is 1. The pointer aj_p indicates the second temporary allocation job information for job J8.

The second provisional allocation job information includes the following information. The pointer next_p is NULL because there is only one temporarily assigned job (job J8 only). jid is the job ID of the temporarily assigned job J8. num_alloc_nids is 2 (because the provisionally assigned compute nodes are the two compute nodes with compute node IDs 4,5).

FIG. 14 is a diagram showing an example of a structure that manages temporary allocation. Temporary allocation management information, temporary allocation information, job allocation information, and job allocation resource information are used for temporary allocation management. The temporary allocation management information, temporary allocation information, job allocation information, and job allocation resource information are stored in the resource information storage unit 130. In FIG. 14, the temporary allocation management information structure 136 (joballocsummaryhead), the temporary allocation information structure 137 (joballocsummary), the job allocation information structure 138 (joballoc), and the job allocation resource information structure 139 (joballocrscinfo). An example is shown.

Structure 136 is an example of a structure of temporary allocation management information. Structure 136 contains the number of temporary allocation information (num_joballocsum) and a pointer to the first temporary allocation information (joballocsummary * head_p). In the temporary allocation management information, temporary allocation information representing a temporary allocation pattern for each job is managed. One temporary allocation information corresponds to one temporary allocation pattern. The number of temporary allocation information is the number of temporary allocation information managed by the relevant temporary allocation management information. The pointer to the first temporary allocation information indicates the storage address of the first temporary allocation information on RAM103. Temporary allocation management information is one instance of structure 136.

Structure 137 is an example of a structure of temporary allocation information. The structure 137 is a pointer to the next temporary allocation information (element) (joballocsummary * next_p), the number of allocated jobs (num_jids), the allocation start time (timespec alloc_start), the allocation completion time (timespec alloc_end), and the first job allocation. Includes a pointer to information (joballoc * head_p) and a pointer to available resource information (availrsc * ar_p).

The pointer to the next temporary allocation information indicates the storage address of the next temporary allocation information on RAM103. The temporary allocation information can manage the temporary allocation of computational resources to a plurality of jobs. The number of assigned jobs is the number of jobs managed by the corresponding temporary allocation information. The allocation start time is the time allocated to the first job among the plurality of temporarily allocated jobs (corresponding to the execution start time of the first job). The allocation completion time is the time allocated to the last job among the plurality of jobs (corresponding to the execution start time of the last job). The pointer to the first job allocation information indicates the storage address of the first job allocation information for the temporarily allocated job on RAM103. The available resource information is the available resource information related to the computational resources used for the provisional allocation. Temporary allocation information is an instance of structure 137. Temporary allocation information can be created for each temporary allocation pattern using structure 137.

Structure 138 is an example of a structure of job allocation information. Structure 138 contains a pointer to the next job allocation information (joballoc * next_p), a job ID (jid), and job allocation resource information (joballocrscinfo ari).

The pointer to the next job allocation information indicates the storage address of the next job allocation information on RAM103. The job ID is the job ID of the temporarily assigned job. The job allocation resource information is information on the allocation status of computational resources for the job indicated by the job ID. Job assignment information is an instance of structure 138. Multiple job allocation information can be created using structure 138.

Structure 139 is an example of a structure of job allocation resource information. Structure 139 includes a resource allocation start time (timespec start), a resource allocation end time (timespec end), the number of allocated resources (num_nids), and a pointer to the allocated node ID (* nids_p).

The resource allocation start time is the calculation resource allocation start time for the job with the job ID included in the job allocation information (execution of the job starts at the start time). The resource allocation end time is the calculation resource allocation end time for the job with the job ID included in the job allocation information (execution of the job is completed at the end time). The number of allocated resources is the number of allocated compute nodes. The assigned node ID is the compute node ID of the allocated compute node. The job allocation resource information is one instance of structure 139. Multiple job allocation resource information can be created using structure 139.

FIG. 15 is a diagram showing an example of temporary allocation of jobs starting from time t1. FIG. 15 shows an example of temporary allocation information corresponding to a pattern in which jobs A, B, C, and D are temporarily allocated starting from time t1.

The provisional allocation information includes the following information. The pointer next_p indicates the next temporary allocation information (Fig. 15 omits the illustration of the next temporary allocation information). For example, each provisional allocation information is concatenated in ascending order of allocation start time (alloc_start). num_jids is 4. This is because it shows temporary allocations for the four jobs A, B, C, and D. alloc_start is t1. This is because the time t1 is the time of the starting point of the provisional allocation (allocation start time). alloc_end is t1 + tA. This is because the execution start time of job D, which is finally started to be executed, is time t1 + tA. The pointer head_p indicates the job allocation information at the beginning. The pointer ar_p indicates the available resource information used for temporary allocation.

FIG. 16 is a diagram showing a management example of a plurality of temporarily assigned jobs. For example, in a pattern in which jobs A, B, C, and D are provisionally assigned starting from time t1, the contents of provisional allocation for each are managed as follows. In this case, job allocation information is created using structure 138 for each of jobs A, B, C, and D (four in total). Each job assignment information is concatenated in descending order of job priority. However, in FIG. 16, the illustration of job allocation information for each of jobs C and D is omitted.

As described above, the temporary allocation information pointer head_p indicates the first job allocation information. Of jobs A, B, C, and D, job A has the highest priority, so the first job allocation information is job allocation information for job A. The job assignment information for job A includes the following information: The pointer next_p indicates the next job allocation information. The job with the next highest priority after job A is job B. Therefore, the next job allocation information for job A is the job allocation information for job B. jid is the job ID (A) of job A.

Further, the job allocation resource information of job A includes the following information. start is t1. end is t1 + tA (because the resource usage time of job A is tA). Here, t1 + tA is an operation for finding the time when the time tA has elapsed from the time t1 (the same applies to the operations for other times). num_nids is 2. This is because the two compute nodes indicated by the compute node IDs 4,5 have been assigned to job A. The pointer nids_p indicates the information of the compute node ID 4,5.

The job allocation information of job B includes the following information. The pointer next_p indicates the next job allocation information. The job with the next highest priority after job B is job C. Therefore, the next job allocation information for job B is the job allocation information for job C. jid is the job ID (B) of job B.

Further, the job allocation resource information of job B includes the following information. start is t1. end is t1 + tB (because the resource usage time of job B is tB). num_nids is 1. This is because one compute node indicated by the compute node ID 6 has been assigned to job B. The pointer nids_p indicates the information of the compute node ID 6.

The job allocation information of job C is the same as the job allocation information of jobs A and B, and is the information corresponding to job C. The job allocation information of job D is the same as the job allocation information of jobs A and B, and is the information corresponding to job D.

FIG. 17 is a diagram showing an example of job information waiting to be executed. The job information 141 waiting to be executed is stored in the job storage unit 140 waiting to be executed. The job information 141 waiting to be executed includes information on the job ID, the execution start time, and the resources used.

The job ID is registered in the job ID item. The execution start time is registered in the execution start time item. The calculation node ID of the calculation node is registered in the item of resources used. For example, information that the job ID is A, the execution start time is t2, and the resources used are 3,4 is registered in the job information 141 waiting to be executed. This indicates that the execution start time of job A is time t2, and the calculation nodes used for execution of job A are the two calculation nodes indicated by the calculation node IDs 3,4. Similarly, information on the execution start time and resources used is registered in the job information 141 waiting to be executed for each of jobs B, C, and D.

FIG. 18 is a diagram showing an example of parameter information. The parameter information 151 is stored in the parameter storage unit 150 in advance. Parameter information 151 includes various types of information used when scheduling jobs. Specifically, the parameter information 151 includes information on the number of subsequent target jobs to be evaluated, the upper limit of the allocation candidate time, and the allocation adoption criteria.

The number of succeeding target jobs to be evaluated is the number of succeeding target jobs to be provisionally allocated, and is, for example, 4. The upper limit of the allocation candidate time is the upper limit of the allocation candidate time with respect to the earliest allocation time, for example, time Δt. If the time t1 is the earliest allocation time, the upper limit of the allocation candidate time is the time (t1 + Δt) after Δt from the time t1.

The allocation adoption standard is a standard for selecting a pattern to be actually adopted from a plurality of temporary allocation patterns of computational resources for each job. For example, the allocation adoption criteria include (1) a large number of provisionally allocated jobs, (2) quick job execution completion, and (3) a small amount of free resources during the target period. Priority is set for the above three. The recruitment criteria in (1) have the highest priority. The recruitment criteria for (2) have the second highest priority. The recruitment criteria in (3) have the lowest priority. The recruitment criteria may be any one of the above plurality. In addition, recruitment criteria other than the illustrated recruitment criteria may be used.

FIG. 19 is a diagram showing an example of the data flow of the management node. FIG. 19 illustrates the relationship between each part illustrated in FIG. 4 and the information referred to or updated by each part. Specifically, the job reception unit 160 adds job information waiting to be assigned. The allocation target job selection unit 171 extracts the allocation target job information from the allocation waiting job information. The succeeding target job selection unit 172 extracts the succeeding target job information from the allocation waiting job information based on the parameter information (the number of succeeding target jobs to be evaluated). The allocation target job selection unit 171 identifies the last succeeding target job information extracted by the succeeding target job selection unit 172 as the information of the terminal job (registers a pointer to the terminal job information in the allocation target job information).

The allocation candidate time detection unit 181 obtains the allocation candidate time and the provisional allocation end time based on the allocation target job information, the parameter information (upper limit of the allocation candidate time), and the available resource information. The allocation candidate time is a candidate time that is the starting point of job allocation. The provisional allocation end time is the time when the upper limit of the allocation candidate time is reached from the time when the highest priority job can be allocated earliest. For example, when the time at which the highest priority job can be assigned earliest is time t1, the temporary allocation end time is time t1 + Δt. The allocation candidate time detection unit 181 selects the allocation candidate time between the time t1 and the time t1 + Δt.

The temporary resource allocation unit 182 temporarily allocates computational resources to each job based on the allocation target job information, subsequent target job information, allocation candidate time, temporary allocation end time, and available resource information (included in the temporary allocation information). To change the temporary allocation information. Here, the temporary resource allocation unit 182 copies the available resource information to the temporary allocation information in accordance with the temporary allocation (in FIG. 19, the copy process is illustrated by reference numeral 182a as the process of the temporary resource allocation unit 182. There is). This is to prevent the production available resource information from being directly updated due to the provisional allocation.

The allocation resource selection unit 183 selects a temporary allocation pattern to be adopted from a plurality of temporary allocation patterns by referring to the temporary allocation information and the parameter information (allocation adoption criteria). The allocated resource selection unit 183 updates the available resource information and the job waiting to be executed information according to the adopted temporary allocation pattern (reflects the contents of the temporary allocation pattern in the actual schedule).

The job execution instruction unit 190 instructs each calculation node to execute a job based on the job information waiting to be executed. Next, the processing procedure by the management node 100 will be described. It is assumed that the allocation target job selection unit 171 and the succession target job selection unit 172 have already created the allocation target job information and the succession target job information.

FIG. 20 is a diagram showing a processing example of the management node. Hereinafter, the processes shown in FIG. 20 will be described along with the step numbers. (S1) The allocation candidate time detection unit 181 detects a plurality of allocation candidate times. Further, the allocation candidate time detection unit 181 obtains the temporary allocation end time. As described above, the provisional allocation end time is the time obtained by adding the upper limit time Δt of the allocation candidate time to the earliest allocation candidate time. The details of the process will be described later.

(S2) The temporary resource allocation unit 182 selects one by one from the beginning (earliest time) to the end (latest time) of the allocation candidate time, and repeats steps S3 and S4. (S3) The temporary resource allocation unit 182 creates temporary allocation information regarding the selected allocation candidate time and stores it in the resource information storage unit 130. Further, the temporary resource allocation unit 182 copies the available resource information used for the temporary allocation process and adds it to the temporary allocation information. The copied available resource information is stored in a predetermined work area of the resource information storage unit 130. After that, the copied available resource information is referred to along with the provisional allocation related to the selected allocation candidate time (the copied available resource information may be updated).

(S4) The temporary resource allocation unit 182 allocates temporary resources for the period from the selected allocation candidate time to the temporary allocation end time, and adds the result to the temporary allocation information. The details of the process will be described later.

(S5) When the temporary resource allocation unit 182 completes the processing of steps S3 and S4 for all of the plurality of allocation candidate times, the processing proceeds to step S6. By executing step S4, one temporary allocation pattern is created for one allocation candidate time. By repeatedly executing step S4 at each allocation candidate time, a plurality of temporary allocation patterns are created.

(S6) The allocation resource selection unit 183 compares a plurality of created temporary allocation patterns and selects one temporary allocation pattern. The allocation resource selection unit 183 selects a temporary allocation pattern based on the allocation adoption criteria included in the parameter information 151.

(S7) The temporary resource allocation unit 182 initializes the work area reserved for temporary resource allocation. FIG. 21 is a flowchart showing an example of allocation candidate time detection. Hereinafter, the processes shown in FIG. 21 will be described along with the step numbers. The following procedure corresponds to step S1 in FIG.

(S11) The allocation candidate time detection unit 181 acquires the first job (highest priority job) from the allocation target job information and the subsequent target job information (list of struct schedjobinfo.head_p) arranged in the order of scheduling priority. .. The allocation candidate time detection unit 181 sets the number of available resources for the first job to 0.

(S12) The allocation candidate time detection unit 181 searches for the earliest time to which the first job can be assigned by the procedure up to step S18. Therefore, the allocation candidate time detection unit 181 selects the time (struct availrsc.time) one by one from the beginning time to the end time of a plurality of available resource information (list of struct availrschead.head_p). Repeat steps S13 to S17. The time selected here is referred to as a "specific time" in steps S13 to S19.

(S13) The allocation candidate time detection unit 181 selects one by one from the plurality of resource information (list of struct availrsc.arihead_p) at a specific time in descending order of available time (struct availrscinfo.availtime), and steps S14 to Repeat S16. In the list of struct availrsc.arihead_p, each resource information is arranged in descending order of available time (struct availrscinfo.availtime).

(S14) The allocation candidate time detection unit 181 determines whether or not the available time of the selected resource information is longer than the resource usage time of the first job. If it is long, the process proceeds to step S15. If it is not long, the process proceeds to step S18. The determination can be made by comparing the available time of resource information (struct availrscinfo.availtime) with the resource usage time of job information (struct jobinfo.reqtime). If No in step S14, the time that can be assigned to the first job cannot be found from the available resource information that is currently being focused on. Therefore, proceed to step S18 to set the time that can be assigned from the next available resource information. You will be searching.

(S15) The allocation candidate time detection unit 181 determines that the computational resource of interest can be used to execute the first job, and counts it as the number of available resources (adds the value of struct availrscinfo.num_nids to the number of available resources). ).

(S16) The allocation candidate time detection unit 181 determines whether or not the count value of the number of available resources for the first job is equal to or greater than the required resource amount of the first job. If it exceeds the required resource amount, the process proceeds to step S19. If it is not more than the required resource amount, the process proceeds to step S17. The determination can be made by comparing the number of available resources for the first job with the required resource amount of job information (struct jobinfo.num_reqnids).

(S17) When the allocation candidate time detection unit 181 finishes processing for all the resource information at the specific time, the process proceeds to step S18. When proceeding to step S18, the allocation candidate time detection unit 181 resets the number of available resources for the first job to 0. When the process proceeds to step S18, it means that the time allottable for the first job could not be obtained from the available resource information currently being focused on.

(S18) The allocation candidate time detection unit 181 normally exits the loop by step S16 at any timing by repeatedly executing steps S13 to S17 while referring to each available resource information in order. .. However, if the allocation candidate time for the first job cannot be detected even after processing all the available resource information that can be searched, the allocation candidate time detection unit 181 outputs error information and performs allocation candidate time detection processing. You may finish.

(S19) The allocation candidate time detection unit 181 determines that the first job can be assigned to the specific time (struct availrsc.time) currently being focused on, and holds the specific time in RAM 103 as the assignable time T1. To do. In the example of the second embodiment, the allottable time T1 = t1. The allocation candidate time detection unit 181 resets the number of available resources for the first job to 0.

(S20) The allocation candidate time detection unit 181 searches for a time after the time T1 to which the first job can be assigned by the procedure up to step S25. Therefore, the allocation candidate time detection unit 181 is charged one by one from the time T1 of the plurality of available resource information (list of struct availrschead.head_p) to the upper limit of the allocation candidate time (= temporary allocation end time T1 + Δt). Select struct availrsc.time) and repeat steps S21-S24. The time selected here is referred to as a "specific time" in steps S21 to S26.

(S21) The allocation candidate time detection unit 181 selects one by one from a plurality of resource information (list of struct availrsc.arihead_p) at a specific time in descending order of available time (avail time), and repeats steps S22 to S24. Execute. In the list of struct availrsc.arihead_p, each resource information is arranged in descending order of available time (struct availrscinfo.availtime).

(S22) The allocation candidate time detection unit 181 determines whether or not the available time of the selected resource information is longer than the resource usage time of the first job. If it is long, the process proceeds to step S23. If it is not long, the process proceeds to step S27. The determination can be made in the same manner as in step S14.

(S23) The allocation candidate time detection unit 181 determines that the computational resource of interest can be used to execute the first job, and counts it as the number of available resources (adds the value of struct availrscinfo.num_nids to the number of available resources). ).

(S24) The allocation candidate time detection unit 181 determines whether or not the count value of the number of available resources for the first job is equal to or greater than the required resource amount of the first job. If it exceeds the required resource amount, the process proceeds to step S26. If it is not more than the required resource amount, the process proceeds to step S25. The determination can be made in the same manner as in step S16.

(S25) When the allocation candidate time detection unit 181 finishes processing for all the resource information at the specific time, the process proceeds to step S27. When proceeding to step S27, the allocation candidate time detection unit 181 resets the number of available resources for the first job to 0. When the process proceeds to step S27, it means that the time allottable for the first job could not be obtained from the available resource information currently being focused on.

(S26) The allocation candidate time detection unit 181 determines that the first job can be assigned to the specific time (struct availrsc.time) of interest, and holds the specific time in the RAM 103 as the assignable time. Then, the process proceeds to step S27.

(S27) The allocation candidate time detection unit 181 ends the allocation candidate time detection processing when the processing for all the available resource information at the time after the allocatable time T1 is completed. The allottable time held in RAM 103 at this stage is the allotment candidate time. For example, the allocation candidate time detection unit 181 detects the time t2, t3, t4 as the allocation candidate time after the time t1 with respect to the assignable time T1 = t1 according to the procedure of steps S20 to S27.

FIG. 22 is a flowchart showing an example of provisional resource allocation. Hereinafter, the process shown in FIG. 22 will be described along with the step numbers. The following procedure corresponds to step S4 in FIG. (S31) The temporary resource allocation unit 182 acquires the available resource information (specified available resource information) corresponding to the allocation candidate time of interest. The temporary resource allocation unit 182 selects the available resource information corresponding to each time (struct availrsc.time) from the start time to the end time among a plurality of available resource information starting from the specified available resource information. Select one by one and process steps S32 and S33 in order. The start time corresponds to the allocation candidate time of interest. The end time corresponds to the latest time (struct availrsc.time) included in the plurality of available resource information that does not exceed the provisional allocation end time. Here, the time of the available resource information selected in step S31 is referred to as a "specific time" in the processing of steps S32 and S33.

(S32) The temporary resource allocation unit 182 selects all jobs (temporary allocation target jobs) that can be assigned to a specific time. Specifically, the temporary resource allocation unit 182 refers to the available resource information at a specific time from the allocation target job information and the subsequent target job information, selects a job that can be allocated, and holds it in RAM 103 as the temporary allocation target job. To do. The details of the process will be described later.

(S33) The temporary resource allocation unit 182 temporarily allocates computational resources to the temporary allocation target job (arrangement of the temporary allocation target job on the time map) based on the temporary allocation target job and the temporary allocation information. The temporary resource allocation unit 182 reflects the result of the temporary allocation in the temporary allocation information. The details of the process will be described later.

(S34) When the temporary resource allocation unit 182 selects the temporary allocation target job and allocates the temporary allocation target job for each time from the start time to the end time, the temporary resource allocation unit 182 starts from the allocation candidate time of interest. End the allocation process.

FIG. 23 is a flowchart showing a selection example of the temporary allocation target job. Hereinafter, the process shown in FIG. 23 will be described along with the step numbers. The following procedure corresponds to step S32 in FIG.

(S101) The temporary resource allocation unit 182 processes the allocation target job information and the subsequent target job information in order of priority. Specifically, the temporary resource allocation unit 182 selects one by one from the plurality of succeeding target job information indicated by the allocation target job information in descending order of priority, and repeatedly executes steps S102 to S110. The subsequent target job information is concatenated in descending order of priority (list of struct schedjobinfo.head_p). Here, the job corresponding to the selected succeeding target job information is referred to as a "target job" in steps S102 to S110. The temporary resource allocation unit 182 sets the number of temporary resource allocations for the target job to 0.

(S102) The temporary resource allocation unit 182 processes resource information in ascending order of available time at a specific time. Specifically, the temporary resource allocation unit 182 selects the resource information one by one in the order of the shortest available time (list of struct availrsc.aritail_p) from the plurality of resource information at a specific time, and steps S103 to Repeat S107.

(S103) The temporary resource allocation unit 182 determines whether the available time (struct availrscinfo.availtime) of the resource information of interest is longer than the resource usage time (struct jobinfo.reqtime) of the succeeding target job information of interest. If the available time is longer, the process proceeds to step S104. If the available time is not longer, the process proceeds to step S108.

(S104) The temporary resource allocation unit 182 determines whether or not there is an unused portion in the temporary allocation in the resource information of interest. If there is an unused part, the process proceeds to step S105. If there are no unused parts, the process proceeds to step S108. Here, the determination in step S104 can be performed by comparing the total number of temporary allocation nodes (struct allocrscinfo.total_alloc_nids) of the temporary allocation work information included in the resource information with the number of available nodes (struct availrscinfo.num_nids) of the resource information. .. If the total number of temporarily allocated nodes is smaller than the number of available nodes, not all computational resources are used for provisional allocation, and unused computational resources remain. On the other hand, if the total number of temporarily allocated nodes matches the number of available nodes, it means that all the computational resources have been used for the provisional allocation and no unused computational resources remain.

(S105) The temporary resource allocation unit 182 counts the computational resources of interest as the number of temporary resources allocated to the target job. Specifically, the number of counts added to the number of temporarily allocated resources is min (number of available resources-number of temporarily allocated resources, number of requested resources of the target job-number of counted temporary allocated resources). Here, the operation min (x, y) is an operation for selecting the smaller of x and y. The number of provisionally allocated resources is the value of struct allocrscinfo.total_alloc_nids of the resource information of interest.

(S106) The temporary resource allocation unit 182 updates the temporary allocation work area of the available resource information. Specifically, the temporary resource allocation unit 182 uses the number of temporary allocation resources counted in step S105 as the total number of temporary allocation nodes (struct allocinfo.total_alloc_nids) in the temporary allocation work area (struct availrscinfo.allocinfo) of the resource information of interest. Add to. As a result, the computational resources temporarily allocated to the target job are managed as used.

(S107) The temporary resource allocation unit 182 determines whether or not the number of temporary resources allocated to the target job matches the required number of resources of the target job. If they match, proceed to step S109 (exit the loop). If they do not match, the process proceeds to step S108. This determination is made by confirming whether or not the number of temporarily allocated resources counted in step S105 has reached the required number of resources of the target job (struct jobinfo.num_reqnids).

(S108) When the temporary resource allocation unit 182 finishes processing all the resource information at the specific time, the process proceeds to step S110. (S109) The temporary resource allocation unit 182 holds information about the target job as a temporary allocation target job. Specifically, the temporary resource allocation unit 182 holds the temporary allocation target job information corresponding to the target job in the RAM 103. The temporary allocation target job information includes the same information as the subsequent target job information. By repeatedly executing step S109, a plurality of temporary allocation target job information indicating a plurality of temporary allocation target jobs can be retained. At this time, the temporary resource allocation unit 182 arranges the temporary allocation target job information in descending order of the job resource usage time (struct jobinfo.reqtime). Then, the process proceeds to step S110.

(S110) The temporary resource allocation unit 182 determines whether or not the current target job has been saved as a temporary allocation target job. If the target job this time is saved as a temporary allocation target job, the process proceeds to step S111. If the target job this time is not saved as a temporary allocation target job, the process proceeds to step S112 (exits the loop). If the target job is not saved as a temporary allocation target job, the reason for not performing temporary allocation of the next job (proceed to step S112) is that the job with low schedule priority is earlier than the job with high schedule priority. This is to prevent it from being executed.

(S111) When the temporary resource allocation unit 182 completes all the processing for the succeeding target job, the processing proceeds to step S112. (S112) The temporary resource allocation unit 182 clears the temporary allocation work area of the available resource information. Specifically, the temporary resource allocation unit 182 clears the temporary allocation work area (struct availrscinfo.allocinfo) of the resource information of interest when the saving of all the temporary allocation target jobs at a specific time is completed.

FIG. 24 is a flowchart showing an arrangement example of the temporary allocation target job. Hereinafter, the processing shown in FIG. 24 will be described along with the step numbers. The following procedure corresponds to step S33 in FIG.

(S121) The temporary resource allocation unit 182 processes the available resource information corresponding to the specific time in order from the resource having the shortest usage time to the resource having the longest usage time. Specifically, the temporary resource allocation unit 182 has one in order from the plurality of resource information indicated by the available resource information, from the resource information having the short available time to the resource information having the long available time (list of struct availrsc.aritail_p). Select one by one and repeat steps S122 to S130. By using the computational resources from the one with the shortest available time, the free time of the computational resources can be reduced.

(S122) The temporary resource allocation unit 182 processes the retained temporary allocation target jobs in descending order of resource usage time. Specifically, the temporary resource allocation unit 182 selects the temporary allocation target job information held in the RAM 103 one by one, and repeatedly executes steps S123 to S129. Here, the temporary allocation target job corresponding to the selected temporary allocation target job information is referred to as a target job in steps S123 to S129. The temporary resource allocation unit 182 sets the number of temporary resource allocation resources of the target job to 0.

(S123) The temporary resource allocation unit 182 determines whether or not the available time (struct availrscinfo.availtime) included in the resource information of interest is longer than the resource usage time (struct jobinfo.reqtime) of the target job. If the available time is longer, the process proceeds to step S124. If the available time is not longer, the process proceeds to step S130.

(S124) The temporary resource allocation unit 182 counts the computational resources of interest as the number of temporary resources allocated to the target job. Specifically, the number of counts added to the number of temporarily allocated resources is min (number of available resources-number of temporarily allocated resources, number of requested resources of the target job-number of counted temporary allocated resources). The number of temporarily allocated resources is the value of struct allocrscinfo.total_alloc_nids of the resource information of interest.

(S125) The temporary resource allocation unit 182 updates the temporary allocation work area of the available resource information. Specifically, the temporary resource allocation unit 182 calculates the number of temporary allocation resources counted in step S124 as the total number of temporary allocation nodes (struct allocrscinfo.total_alloc_nids) in the temporary allocation work area (struct availrscinfo.allocinfo) of the resource information of interest. Add to. As a result, the computational resources temporarily allocated to the target job are managed as used. Further, the temporary resource allocation unit 182 also reflects the job ID and the amount of resources used (number of acquired resources) that use the computational resource in the temporary allocation work area in preparation for the processing after step S132 (structure 135). Equivalent to information).

(S126) The temporary resource allocation unit 182 determines whether or not the number of temporary resources allocated to the target job matches the required number of resources of the target job. If they match, the process proceeds to step S127. If they do not match, the process proceeds to step S130. This determination can be made by checking whether the counted number of temporarily allocated resources has reached the required number of resources of the target job (struct jobinfo.num_reqnids).

(S127) The temporary resource allocation unit 182 deletes the target job (corresponding job) currently being focused on from the temporary allocation target job. Specifically, the temporary resource allocation unit 182 deletes the temporary allocation target job information corresponding to the target job currently being focused on from the plurality of temporary allocation target job information held in the RAM 103.

(S128) The temporary resource allocation unit 182 determines whether or not there is a temporary allocation target job. If there is a temporary allocation target job, the process proceeds to step S129. If there is no temporary allocation target job, the process proceeds to step S132. Specifically, if the temporary allocation target job information held in the RAM 103 remains, there is a temporary allocation target job. On the other hand, if the plurality of temporary allocation target job information held in the RAM 103 are all deleted by repeatedly executing step S127, there is no temporary allocation target job.

(S129) The temporary resource allocation unit 182 checks the temporary allocation work area (struct availrscinfo.allocinfo) of the available resource information, and determines whether or not there is an unused part in the temporary allocation in the available resources of interest. To do. If there is an unused part, the process proceeds to step S130. If there are no unused parts, that is, all of them have been used by temporary allocation, the process proceeds to step S131. Specifically, if the total number of temporary allocation nodes (struct allocrscinfo.total_alloc_nids) in the temporary allocation work area of the resource information of interest is smaller than the number of available nodes of resource information (struct availrscinfo.num_nids), the temporary allocation is performed. There is an unused part. On the other hand, if the total number of temporarily allocated nodes matches the number of available nodes, all the relevant resource information has already been used for temporary allocation (moving to the next processing of resource information).

(S130) The temporary resource allocation unit 182 moves to the processing of the next temporary allocation target job (proceed to step S122). If the temporary resource allocation unit 182 has processed all the temporary allocation target jobs, the temporary resource allocation unit 182 proceeds to step S131.

(S131) The temporary resource allocation unit 182 moves to the processing of the next resource information (proceed to step S121). Note that the temporary resource allocation unit 182 may output an error and end the process when there is no resource information for determining the allocation destination even though the temporary allocation target job remains.

(S132) The temporary resource allocation unit 182 updates the temporary allocation information (struct joballoc summary) based on the information in the temporary allocation work area (temporary allocation work information). (S133) The temporary resource allocation unit 182 updates the available resource information based on the temporary allocation information. Specifically, the temporary resource allocation unit 182 updates the available resource information from the temporary allocation information updated in step S132 in order to perform processing after the next time. As mentioned in step S3 of FIG. 20, the update is made to the copied available resource information. The temporary resource allocation unit 182 may create available resource information for a new time according to the temporary allocation status of the temporary allocation target job. For example, the temporary resource allocation unit 182 uses the first half of the available time for temporary allocation of existing resource information, and if the latter half is unused for temporary allocation, it is new to the start time of the latter half. Create available resource information.

FIG. 25 is a flowchart showing an example of allocation resource selection. Hereinafter, the processes shown in FIG. 25 will be described along with the step numbers. The following procedure corresponds to step S6 in FIG. (S41) The allocation resource selection unit 183 acquires the temporary allocation information at the beginning and holds it as the selection allocation information. Specifically, the allocation resource selection unit 183 first extracts the first temporary allocation information (struct joballocsummaryhead.head_p) and holds it in the RAM 103 as selective allocation information in order to compare all the temporary allocation information.

(S42) The allocation resource selection unit 183 processes the provisional allocation information in order. Specifically, the allocation resource selection unit 183 selects temporary allocation information (list of struct joballocsummaryhead.head_p) excluding the temporary allocation information at the beginning one by one, and repeatedly executes steps S43 to S45. The temporary allocation information selected here is referred to as "temporary allocation information of interest" in the subsequent steps.

(S43) The allocation resource selection unit 183 compares the selective allocation information and the provisional allocation information of interest based on the allocation adoption criteria included in the parameter information 151. (S44) The allocation resource selection unit 183 determines whether or not the provisional allocation information of interest has priority over the selection allocation information in light of the recruitment criteria. If the temporary allocation information of interest has priority, the process proceeds to step S45. If the temporary allocation information of interest is not prioritized, the process proceeds to step S46. For example, the allocation adoption criteria for parameter information 151 give priority to (1) many jobs that could be provisionally allocated, (2) jobs that are completed quickly, and (3) those that have a small amount of free resources during the target period. Indicates that. That is, the allocation resource selection unit 183 first gives priority to the one with the larger number of jobs that can be provisionally allocated. If the number of jobs that can be provisionally assigned is the same, priority is given to the one that completes the execution of all jobs earlier. If the execution completion of all jobs is at the same time, priority is given to the one with the smaller amount of free resources in the target period (the period until the execution completion time). The amount of free resources can be expressed as the node time product of free resources during the period.

(S45) The allocation resource selection unit 183 holds the temporary allocation information of interest as the selection allocation information. That is, the allocation resource selection unit 183 holds the temporary allocation information of interest as the selection allocation information instead of the current selection allocation information.

(S46) When the allocation resource selection unit 183 processes all the provisional allocation information, the process proceeds to step S47. (S47) The allocated resource selection unit 183 updates the available resource information from the selective allocation information. Specifically, the allocated resource selection unit 183 updates the available resource information (struct availrschead.head_p) based on the temporary allocation pattern (selective allocation information) that should be given the highest priority. Here, the available resource information of the update destination is not the available resource information copied in step S3, but the available resource information of the copy source. That is, the content of the allocation pattern determined from the plurality of temporary allocation patterns is reflected in the actual available resource information.

(S48) The allocation resource selection unit 183 saves the allocation result in the job information waiting to be executed. Specifically, the job execution schedule is added to the pending job information according to the determined allocation pattern.

In this way, the management node 100 creates a plurality of temporary allocation patterns, and selects the one that best matches the recruitment criteria from the plurality of temporary allocation patterns. The predetermined period of the recruitment criteria may be a period up to the upper limit of the allocation candidate time, or may be specified in advance as a period different from the period up to the upper limit of the allocation candidate time.

Next, a specific example of allocating computational resources to jobs A, B, C, and D by the management node 100 will be described. FIG. 26 is a diagram showing specific examples of available resource information and job information. First, as illustrated in FIG. 5, it is assumed that jobs J1, J2, J3, J4, J5, J6, and J7 have already been scheduled. The jobs to be assigned this time are jobs A, B, C, and D. At this time, the available resource information 132a includes the following information.

At time t0, no computational resources are available. At time t1, two types of computational resources are available. The first is the time zone from time t1 to time t3-t1 of one calculation node with calculation node ID 6. The second is the time zone of the two calculation nodes with the calculation node IDs 4 and 5 without an upper limit from the time t1.

At time t2, three types of computational resources are available. The first is the time zone from time t2 to time t3-t2 of the two calculation nodes with the calculation node IDs 6 and 7. The second is the time zone from time t2 to time t4-t2 of one calculation node with calculation node ID 3. The third is the time zone of the two calculation nodes with the calculation node IDs 4 and 5 without an upper limit from the time t2.

The available resource information 132a also includes information on available computational resources at times t3, t4, and t5. Further, the allocation target job information 121a includes a pointer indicating job information (subsequent target job information) of job A as the first job information. Job A has a required resource amount of "2" and a resource usage time of "tA". The allocation target job information 121a includes a pointer indicating job D information (subsequent target job information) as the terminal job information (not shown in FIG. 26).

Subsequent target job information 122a includes information on each job. The information of each job is linked by pointers in descending order of priority. Subsequent target job information 122a includes information on jobs B, C, and D. Job B has a required resource amount of "1" and a resource usage time of "tB". Job B is the next highest priority job after job A. Job C has a required resource amount of "1" and a resource usage time of "tC". Job C is the next highest priority job after job B. Job D has a required resource amount of "1" and a resource usage time of "tD". Job D is the next highest priority job after job C.

FIG. 27 is a diagram showing a detection example of the allocation candidate time. The allocation candidate time detection unit 181 detects the allocation candidate time by the job A having the highest priority among the jobs A, B, C, and D. For example, time t0 cannot be a candidate time for allocation of job A because there are no available computational resources.

At time t1, there are computational resources with "2" available nodes and no limit on available time (""). tA &lt;. This computational resource satisfies the requirements of the required resource amount 2 of job A and the resource usage time tA. Therefore, the time t1 is a time at which job A can be assigned and is a candidate time for allocation.

At time t2, there are computational resources with the number of available nodes 2 and the available time t3-t2. However, tA&gt; t3-t2. That is, since the computational resource does not satisfy the requirement of the resource usage time tA, job A cannot be assigned to the computational resource. In addition, at time t2, there are computational resources with the number of available nodes "2" and no limit on the available time. This computational resource satisfies the requirements of the required resource amount 2 of job A and the resource usage time tA. Therefore, the time t2 is a time at which job A can be assigned and is a candidate time for allocation.

In this way, the allocation candidate time detection unit 181 sequentially detects the allocation candidate time. Here, the allocation candidate time detection unit 181 does not detect the allocation candidate time by selecting an unlimited number of future times. An upper limit is set for the allocation candidate time so that the execution of job A is not delayed more than a certain amount and scheduling can be performed efficiently.

FIG. 28 is a diagram showing an example of the upper limit time of the allocation candidate time. The parameter information 151 includes the upper limit Δt of the allocation candidate time. The allocation candidate time detection unit 181 calculates the time (allocation end time) that is the upper limit of the allocation candidate time by using the earliest allocation candidate time t1 and Δt determined for the job A having the highest priority. .. Specifically, the upper limit of the allocation candidate time is t1 + Δt. In the case of this example, the time t1 + Δt is later than the time t4 and earlier than the time t5. Therefore, the allocation candidate time detection unit 181 detects the times t1, t2, t3, and t4 as the allocation candidate times. Since the time t5 is later than the upper limit time t1 + Δt, it is excluded from the allocation candidate times.

FIG. 29 is a diagram showing a selection example of the temporary allocation target job. The temporary resource allocation unit 182 pays attention to one allocation candidate time, and from the jobs A, B, C, and D to be allocated this time, the upper limit time (t1 + Δt) starting from the allocation candidate time. Select the temporary allocation target job for each time included in the time range up to. For example, when focusing on the allocation candidate time t1, the temporary resource allocation unit 182 first selects the temporary allocation target job for the time t1. Jobs to be provisionally assigned are selected according to the order of priority of each job.

More specifically, the temporary resource allocation unit 182 refers to the resource information of the time t1 in available resource information 132a, di perform job A, B, C, the selection of the tentative allocation target jobs in the order of D. First, job A can be assigned two calculation nodes with calculation node IDs 4 and 5 at time t1. Therefore, job A is a temporary allocation target job at time t1.

Next, job B can be assigned one compute node with the compute node ID 6 at time t1. This is because the resource usage time tB of job B is tB &lt;t3-t1. Therefore, job B is a temporary allocation target job at time t1.

In this case, at time t1, all available compute nodes have been selected for jobs A and B. Therefore, there is no compute node that can be assigned to jobs after job C. Therefore, jobs C and D are not temporary allocation target jobs at time t1.

FIG. 30 is a diagram showing a selection example (continued) of the temporary allocation target job. The process of FIG. 29 can also be described as illustrated in FIG. First, the temporary resource allocation unit 182 determines that the calculation node with the calculation node ID 4,5 can be assigned to the job A at time t1 based on the available resource information 132a. The temporary resource allocation unit 182 determines job A as a temporary allocation target job for time t1.

Next, the temporary resource allocation unit 182 determines that the calculation node with the calculation node ID 6 can be assigned to the job B at time t1 based on the available resource information 132a. The temporary resource allocation unit 182 determines job B as a temporary allocation target job for time t1.

At this point, there are no compute nodes that can be assigned to other jobs at time t1. Therefore, the temporary resource allocation unit 182 does not select jobs C and D as temporary allocation target jobs at time t1. Therefore, in this case, the jobs selected as the temporary allocation target jobs are jobs A and B. Then, the temporary resource allocation unit 182 executes temporary allocation to the computational resource at time t1 for the temporary allocation target jobs A and B.

FIG. 31 is a diagram showing an example of temporary allocation. During the temporary allocation process, the temporary resource allocation unit 182 searches for jobs that can be allocated in ascending order of available time of available computational resources. Here, the temporary resource allocation unit 182 searches for a job from the temporary allocation target jobs A and B specified for the time t1. At this time, the temporary resource allocation unit 182 gives priority to the job having a long resource usage time among the temporary allocation target jobs.

More specifically, the available resource information 132a includes two types of resource information, that is, available time t3-t1 and available time , as computational resources that can be used at time t1. The temporary resource allocation unit 182 searches for a job to which the computational resource with the shorter available time (available time t3-t1) is allocated. As mentioned above, the job search order is in the order of longest resource usage time (since tA&gt; tB, the order is A, B). In this case, the resource usage time tA of job A is tA&gt; t3-t1. Therefore, job A cannot be assigned. Next, the resource usage time tB of job B is tB &lt;t3-t1. Therefore, job B can be assigned. In this way, the temporary resource allocation unit 182 allocates the calculation node of the calculation node ID 6 at time t1 to the job B which is the temporary allocation target job. Next, in the same manner, the temporary resource allocation unit 182 allocates the calculation nodes of the calculation node IDs 4 and 5 at the time t1 to the job A which is the temporary allocation target job.

FIG. 32 is a diagram showing an example (continued) of temporary allocation. The process of FIG. 31 can also be described as illustrated in FIG. First, the temporary resource allocation unit 182 searches the temporary allocation target jobs A and B for jobs to be assigned to the calculation node with the calculation node ID 6 at time t1. In jobs A and B to be provisionally allocated, job A has a longer resource usage time than job B (tA&gt; tB). Therefore, the temporary resource allocation unit 182 attempts to allocate job A to the calculation node with the calculation node ID 6 at time t1, but cannot allocate job A because it does not satisfy the request for the resource usage time of job A. .. Next, the temporary resource allocation unit 182 attempts to allocate job B to the calculation node with the calculation node ID 6 at time t1, determines that the request for the resource usage time of job B is satisfied, and makes the calculation for job B. Assign a node. Subsequently, the temporary resource allocation unit 182 allocates the temporary allocation target job A to the calculation nodes with the calculation node IDs 4 and 5 at time t1 (the remaining temporary allocation target job is only job A).

In this way, the temporary resource allocation unit 182 completes the temporary allocation of the computational resources to the temporary allocation target job at time t1. Then, the temporary resource allocation unit 182 updates the available resource information 132a according to the result of the temporary allocation.

FIG. 33 is a diagram showing an example of available resource information after updating. The temporary resource allocation unit 182 reflects the result of allocating jobs A and B at time t1 in the available resource information 132a. Specifically, the temporary resource allocation unit 182 adds that the calculation node with the calculation node ID 6 is assigned to the job B in the resource information at time t1. In addition, the temporary resource allocation unit 182 adds that the two calculation nodes with the calculation node IDs 4 and 5 have been assigned to the job A in the resource information at time t1.

Further, the temporary resource allocation unit 182 adds the information for the time t1 + tB to the available resource information 132a (the structure 132 and the instance of the structure 133 included in the structure 132 are added). Specifically, at time t1 + tB, resource information such as the number of available nodes is "2", the available time is "t3-t1-tB", and the node IDs are "6" and "7" is added. Also, at time t1 + tB, resource information such as the number of available nodes is "1", the available time is "t4-t1-tB", and the node ID is "3" is added. The available resource information 132b exemplifies after the resource information is added to the available resource information 132a.

Similarly, the temporary resource allocation unit 182 also adds information for time t1 + tA to the available resource information 132a (however, not shown in FIG. 33). In this way, the temporary resource allocation unit 182 selects a temporary allocation target job for the next time from the remaining jobs C and D based on the updated available resource information 132b, and calculates resources for the selected job. Perform temporary allocation of. The temporary resource allocation unit 182 repeatedly executes the above process to obtain a temporary allocation pattern for the job for each allocation candidate time.

FIG. 34 is a diagram showing an example of a temporary allocation pattern. FIG. 34 (A) illustrates the provisional allocation pattern Pt1 for the allocation candidate time t1. Specifically, the temporary resource allocation unit 182 finishes allocating the computational resources at time t1 to jobs A and B by the method illustrated in FIGS. 32 and 33, and then allocates the computational resources at time t2 to job C (calculation). Assign node ID 7). Further, the temporary resource allocation unit 182 allocates the computational resource (computational node ID 4) at time t1 + tA to job D. In this way, the temporary resource allocation unit 182 obtains the temporary allocation pattern Pt1. Note that the calculation node of either the calculation node ID 4 or the calculation node ID 5 is assigned to the job D among the calculation resources at time t1 + tA. If the available computational resources are the same for both compute node IDs 4 and 5, for example, the smaller compute node ID is preferentially assigned (the same applies in the following cases).

FIG. 34 (B) illustrates the provisional allocation pattern Pt2 for the allocation candidate time t2. In the case of the allocation candidate time t2, the temporary resource allocation unit 182 selects jobs A, B, C, and D as the temporary allocation target jobs at the time t2. Then, the temporary resource allocation unit 182 allocates the calculation node with the calculation node ID 6 to the job B. The temporary resource allocation unit 182 allocates the calculation node with the calculation node ID 7 to job C. The temporary resource allocation unit 182 allocates two calculation nodes with calculation node IDs 3 and 4 to job A. The temporary resource allocation unit 182 allocates the calculation node with the calculation node ID 5 to job D.

FIG. 34 (C) illustrates the provisional allocation pattern Pt3 for the allocation candidate time t3. When the allocation candidate time is t3, the temporary resource allocation unit 182 selects job A as the temporary allocation target job at time t3. Then, the temporary resource allocation unit 182 allocates the two calculation nodes 4 and 5 to the job A. At time t3, the calculation node 3 can also be used, but since time t4-t3 is shorter than the resource usage time tB of job B (tB &lt;t4-t3), jobs other than job A are assigned at time t3. Cannot be assigned. The time t3 + tA is later than the time t1 + Δt. Therefore, the temporary resource allocation unit 182 does not temporarily allocate jobs other than job A (other than job A is not assigned to the temporary allocation pattern Pt3).

A temporary allocation pattern is also created for the allocation candidate time t4. The temporary allocation pattern for the allocation candidate time t4 is a pattern in which job A is arranged starting from the allocation candidate time t4 (not shown). Moreover, since the time t4 + tA is later than the time t1 + Δt, the temporary allocation of jobs other than the job A is not performed as in the case of the allocation candidate time t3 (temporary allocation for the allocation candidate time t4). Only job A is placed in the pattern).

FIG. 35 is a diagram showing an example of temporary allocation information (pattern Pt1). The temporary allocation information 137a and the job allocation information group 138a are specific examples of information indicating the temporary allocation pattern Pt1.

Temporary allocation information 137a includes the following information. The allocation start time is t1. The allocation completion time is t1 + tA (corresponding to the time when the execution of the last job D starts). The number of assigned jobs is 4. This is because it is the result of provisionally assigning a total of four jobs, jobs A, B, C, and D. Further, the temporary allocation information 137a includes a pointer indicating the job allocation information (information of job A) at the beginning of the job allocation information group 138a. The job allocation information group 138a includes job allocation information for each of jobs A, B, C, and D. Each job assignment information is linked by a pointer in the order of priority.

Job assignment information for job A includes the following information: The allocation start time is t1. The allocation end time is t1 + tA. The number of allocated resources is 2. The allocated resource (calculation node ID) is 4,5.

The job assignment information for job B includes the following information: The allocation start time is t1. The allocation end time is t1 + tB. The number of allocated resources is 1. The allocated resource (calculation node ID) is 6.

Job assignment information for job C includes the following information: The allocation start time is t2. The allocation end time is t2 + tC. The number of allocated resources is 1. The allocated resource (calculation node ID) is 7.

The job assignment information for job D includes the following information: The allocation start time is t1 + tA. The allocation end time is t1 + tA + tD. The number of allocated resources is 1. The allocated resource (calculation node ID) is 5.

FIG. 36 is a diagram showing an example of temporary allocation information (pattern Pt2). The temporary allocation information 137b and the job allocation information group 138b are specific examples of information indicating the temporary allocation pattern Pt2.

Temporary allocation information 137b includes the following information. The allocation start time is t2. The allocation completion time is t2. In the case of the temporary allocation pattern Pt2, since all the jobs of jobs A, B, C, and D are assigned to the time t2, the allocation start time and the allocation completion time are both t2. The number of assigned jobs is 4. This is because it is the result of provisionally assigning a total of four jobs, jobs A, B, C, and D. Further, the temporary allocation information 137b includes a pointer indicating the job allocation information (information of job A) at the beginning of the job allocation information group 138b. The job allocation information 137b includes job allocation information for each of jobs A, B, C, and D. Each job assignment information is linked by a pointer in the order of priority.

Job assignment information for job A includes the following information: The allocation start time is t2. The allocation end time is t2 + tA. The number of allocated resources is 2. The allocated resource (calculation node ID) is "3,4".

The job assignment information for job B includes the following information: The allocation start time is t2. The allocation end time is t2 + tB. The number of allocated resources is 1. The allocated resource (calculation node ID) is 6.

Job assignment information for job C includes the following information: The allocation start time is t2. The allocation end time is t2 + tC. The number of allocated resources is 1. The allocated resource (calculation node ID) is 7.

The job assignment information for job D includes the following information: The allocation start time is t2. The allocation end time is t2 + tD. The number of allocated resources is 1. The allocated resource (calculation node ID) is 5.

Temporary allocation patterns for each of the allocation candidate times t3 and t4 can be managed in the same manner as the temporary allocation patterns Pt1 and Pt2. By comparing the information of each temporary allocation pattern described above, the allocation resource selection unit 183 compares the number of jobs executed within the predetermined time range, the execution completion time, the ratio of the free time of the calculation node, and the like in each temporary allocation pattern. It is possible.

The allocation resource selection unit 183 selects the highest priority temporary allocation pattern from the plurality of temporary allocation patterns based on the information of the allocation adoption criteria included in the parameter information 151. For example, according to the criteria that the number of temporary allocation jobs is large, the number of temporary allocation jobs is 4 at candidate times t1 and t2, while the number of temporary allocation jobs is 1 at candidate times t3 and t4. .. Therefore, the two temporary allocation patterns for the candidate times t3 and t4 have a lower priority than the temporary allocation patterns Pt1 and Pt2 for the candidate times t1 and t2. Therefore, the allocation resource selection unit 183 excludes the two temporary allocation patterns for the candidate times t3 and t4 from the selection candidates.

Next, the allocation resource selection unit 183 compares the provisional allocation patterns Pt1 and Pt2 according to the allocation adoption criteria. In both the temporary allocation patterns Pt1 and Pt2, the number of temporary allocation jobs is 4, which is the same. Therefore, the allocation resource selection unit 183 selects either one of the temporary allocation patterns Pt1 and Pt2 based on the criterion that the job execution is completed quickly. Here, in the temporary allocation pattern Pt2, the time at which the execution of all the jobs A, B, C, and D is completed is earlier than that in the temporary allocation pattern Pt1.

Specifically, in each of the temporary allocation patterns Pt1 and Pt2, the last job to be executed is job D. According to the job allocation information group 138a, in the temporary allocation pattern Pt1, the allocation end time of job D is t1 + tA + tD. Further, according to the job allocation information group 138b, in the temporary allocation pattern Pt2, the allocation end time of job D is t2 + tD. The time t2 + tD is earlier than the time t1 + tA + tD. Therefore, the allocation resource selection unit 183 determines that the temporary allocation pattern Pt2 has a higher selection priority than the temporary allocation pattern Pt1.

Finally, the allocated resource selection unit 183 adopts the provisional allocation pattern Pt2 as the allocation of computational resources to jobs A, B, C, and D. The allocation resource selection unit 183 reflects the contents of the selected temporary allocation pattern Pt2 in the job information 141 waiting to be executed. In this way, jobs A, B, C, and D are executed by the plurality of calculation nodes according to the schedule corresponding to the selected temporary allocation pattern Pt2.

According to the management node 100, job execution can be streamlined. For example, a method of sequentially executing each prioritized job at the earliest time when the prioritized jobs can be executed can be considered. However, simply allocating jobs at the earliest time according to priority does not necessarily mean that computational resources are efficiently allocated to each job. It may take longer to complete all jobs.

Therefore, the management node 100 also considers subsequent jobs B, C, and D when scheduling job A, which has the highest priority. Specifically, the management node 100 acquires a plurality of temporary allocation patterns that are candidates for scheduling of jobs A, B, C, and D, and compares the plurality of patterns to increase the number within a predetermined period according to the parameter information 151. Adopt a pattern that can execute the job of. The management node 100 allocates jobs to each calculation node according to the adopted temporary allocation pattern. For example, in the temporary allocation pattern Pt2, the time until all the executions of jobs A, B, C, and D are completed can be made earlier than that in the temporary allocation pattern Pt1. In addition, the temporary allocation pattern Pt2 can reduce the free time of the calculation node as compared with the temporary allocation pattern Pt1. Therefore, the throughput of job execution can be improved while maintaining the priority of the job. In this way, job execution can be streamlined.

The information processing of the first embodiment can be realized by causing the arithmetic unit 1b to execute the program. Further, the information processing of the second embodiment can be realized by causing the CPUs 101 and 102 to execute the program. The program can be recorded on a computer-readable recording medium 13.

For example, the program can be distributed by distributing the recording medium 13 on which the program is recorded. Alternatively, the program may be stored in another computer and distributed via the network. For example, the computer may store (install) a program recorded on the recording medium 13 or a program received from another computer in a storage device such as RAM 103 or HDD 104, read the program from the storage device, and execute the program. Good.

The following additional notes will be further disclosed with respect to the embodiments including the above-mentioned first and second embodiments. (Appendix 1) A storage unit that stores information on the available time zones of multiple compute nodes, Based on the above information, the first time during which the highest priority job among the plurality of jobs can be executed is obtained, and the first time is a candidate for the execution start time of the highest priority job later than the first time. If there is a second time in which more jobs can be executed within a predetermined time range than the time of executing the highest priority job, the highest priority job and other jobs are selected from the second time. An arithmetic unit that assigns the plurality of jobs to the plurality of calculation nodes to be executed, and Information processing device with.

(Appendix 2) The calculation unit selects candidates for allocation patterns of the plurality of jobs to the plurality of calculation nodes when the execution of the highest priority job is started at each of the first time and the second time. The information processing apparatus according to Appendix 1, wherein the information to be shown is generated, and the top priority job is selected at the first time or the second time according to the comparison of the candidates of the allocation pattern.

(Appendix 3) The calculation unit compares the times when the execution of all the plurality of jobs is completed based on the candidates of the allocation pattern, and selects the time when the highest priority job is executed according to the comparison. Information processing device described in Appendix 2.

(Supplementary note 4) The calculation unit compares the amount of free time of the plurality of calculation nodes based on the candidate of the allocation pattern, and selects the time to execute the highest priority job according to the comparison. Information processing device according to 2 or 3.

(Appendix 5) When the calculation unit starts executing the highest priority job at each of the plurality of candidate times that are candidates for the second time, the allocation pattern of the plurality of jobs to the plurality of calculation nodes The information processing apparatus according to Appendix 2, which generates information indicating candidates and selects a time to execute the highest priority job according to a comparison of candidates of the allocation pattern.

(Appendix 6) The first time is the earliest time in which the highest priority job can be executed. The information processing apparatus according to Appendix 5, wherein the calculation unit determines an upper limit time of the plurality of candidate times based on the first time.

(Appendix 7) The storage unit stores information on the required resources indicating the number of calculation nodes required to execute each of the plurality of jobs and the usage time of the calculation nodes. The arithmetic unit identifies the first and second times based on the available time zones of the plurality of computing nodes and the required resources of each of the plurality of jobs. The information processing device according to any one of Appendix 1 to 6.

(Appendix 8) Multiple compute nodes to which multiple jobs can be assigned, and Based on the information of the available time zone of the plurality of compute nodes, the first time in which the highest priority job among the plurality of jobs can be executed is obtained, and the highest priority is later than the first time. If there is a second time that is a candidate for the job execution start time and can execute more jobs within a predetermined time range than executing the highest priority job from the first time, the second time To the management node that allocates the plurality of jobs to the plurality of compute nodes so as to execute the highest priority job and other jobs from Parallel computer system with.

(Appendix 9) On the computer, Based on the information of the available time zone of multiple compute nodes, the first time when the highest priority job among multiple jobs can be executed is calculated. It is a candidate for the execution start time of the highest priority job later than the first time, and more jobs can be executed within a predetermined time range than the execution of the highest priority job from the first time. If there is a time of 2, the plurality of jobs are assigned to the plurality of calculation nodes so that the highest priority job and other jobs are executed from the second time. A job schedule setting program that executes processing.

(Appendix 10) The computer Based on the information of the available time zone of multiple compute nodes, the first time when the highest priority job among multiple jobs can be executed is calculated. It is a candidate for the execution start time of the highest priority job later than the first time, and more jobs can be executed within a predetermined time range than the execution of the highest priority job from the first time. If there is a time of 2, the plurality of jobs are assigned to the plurality of calculation nodes so that the highest priority job and other jobs are executed from the second time. Job schedule setting method.

1 Information processing device 1a Memory 1b Arithmetic unit 2,3,4 compute nodes