Problem Statement |
| | Introduction
You are working on a large, distributed scientific application. The application receives input at the beginning of execution, and then performs a number of computations. There are a number of components (or jobs) in the application, and some components are dependent on others meaning they can't be started until the others finish. The entire computation can best be expressed as a directed, acyclic graph. A node in the graph represents a component, which is dependent on the components from which it has edges. In addition to the graph topology, each node is labeled with a number giving the number of floating point operations (FLOPs) it will require.
You will be given a description of this graph as input. Additionally, you will be given the speeds of a number of machines, in FLOPs per millisecond. If a job is dependent on another job, and the two jobs are run on different machines, there must be a gap of transfer milliseconds between the end of the first job and the start of the second. If the two jobs are run on the same machine, there need be no gap.
Your task, naturally, is to run the computation as quickly as possible. Thus, you must return a schedule, assigning each component to one machine, and specifying the order to run the components on the machines. In your schedule, you may run one component for a while, pause it, run a different one, and then pick up where you left off with the first one. However, pausing and resuming takes some time. You may not transfer a component from one machine to another.
Input
The input will be given to you as a int[] machines, describing each machine in terms of FLOPs per millisecond, and a String[] jobs. Each element of jobs will be formatted as "FLOPs PAUSE JOB1 JOB2 ... JOBk". FLOPs gives you the number of FLOPs required by this job, while PAUSE tells you how long it will take to pause or resume (they take the same amount of time) the job, in milliseconds. JOBi gives you the ID of a job (indexed from 0) that must be completed prior to this job starting.
Output
You should return a String[] where each element is an interval to run a job on a machine. The elements should be formatted as:
TIMEstart TIMEend J M
specifying a run of job J on machine M (indexed from 0) in the specified time interval.
Tests
Each test will be generated by first picking two constants uniformly: p in [0.0,0.05] and pow in [0,2]. transfer will be chosen uniformly in [1,1000]. The number of machines will then be chosen uniformly in [10,100], while the number of jobs will be chosen in [10,500000]. Each machine will have a speed uniformly chosen in [1000,10000]. Each job will have a pause time uniformly chosen in [1,10000]. The size of each job will be chosen in [1E3,1E9] according to a power law distribution with exponent pow. For each (i,j) such that i < j and i >= j-1000, job j will depend on i with probability p.
Scoring
For each test case, we will compute the number of milliseconds you take, beyond the lowest time on that test case out of all competitors. We will simply sum this over all test cases (and add 1 so that your score can't be 0). If the leader (with the lowest sum) has a sum of S, and you have a sum of T, your score will be sqrt(S/T)*100. If you fail on a test case, 1E9 will be added to your sum for that case.
Tools
ProcessorScheduling.java
ProcessorScheduling.jar
A very basic tool is provided to let you run tests locally. You should write a program that reads parameters from standard in, formatted like:
M J transfer
machine[0]
machine[1]
...
machine[M-1]
jobs[0]
jobs[1]
...
jobs[J-1]
In other words, the first line contains three integers, the next M lines contain the machine input, and the final J lines contain the jobs input. You should output your result as:
LEN
result[0]
result[1]
...
result[LEN-1]
In other words, an integer followed by the elements of your return. The tool can be run from the command line as:
java -Xmx1024M -jar ProcessorScheduling.jar <command> <seed>
<command> is the command for your executable, while <seed> defines the test paramters (the examples are seeds 1-10). Anything you print to standard error in your program will be shown on the console (be sure not to print anything other than what is specified above to standard out).
|
| |
Definition |
| | | Class: | ProcessorScheduling | | Method: | schedule | | Parameters: | int[], String[], int | | Returns: | String[] | | Method signature: | String[] schedule(int[] machines, String[] jobs, int transfer) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | If you allocate multiple intervals for one job, the pause and resume time will be included in the intervals. For example, if the pause time is one, and you allocate 1-5, 9-12, and 15-19 your program will run from 1-4, pause from 4-5, resume from 9-10 run from 10-11, pause from 11-12, resume from 15-16 and run from 16-19. |
| - | The time limit is 15 seconds. |
| - | The memory limit is 1024M. |
| - | The thread limit is 32, including your primary thread. The machines have 8 cores, and thus you can potentially do much more computation by threading. |
| - | If your solution is invalid in any way (overlapping intervals, starting a job before its requirements are finished, invalid formatting, etc) you will fail that case. |
| - | The order of the jobs will be unchanged from the test case generation. Thus, they will be given to you sorted topologically. |
| - | No job may run beyond time 1E10. |
| - | The start and end times of each of your intervals must be integers. |
| |
Examples |
| 0) | |
| | | Returns:
"p = 0.02945198102051495<br>
pow = 0.7984954674161717<br>
jobs = 217212<br>
machines = 84<br>
transfer = 307<br>
" | |
|
| 1) | |
| | | Returns:
"p = 0.022017740201681367<br>
pow = 0.0512270939535211<br>
jobs = 28793<br>
machines = 52<br>
transfer = 193<br>
" | |
|
| 2) | |
| | | Returns:
"p = 0.04084870687857926<br>
pow = 0.23936634704587667<br>
jobs = 284560<br>
machines = 20<br>
transfer = 581<br>
" | |
|
| 3) | |
| | | Returns:
"p = 0.043578829942208575<br>
pow = 0.3477121219273487<br>
jobs = 299706<br>
machines = 77<br>
transfer = 919<br>
" | |
|
| 4) | |
| | | Returns:
"p = 0.021666605038956104<br>
pow = 0.09719726359971026<br>
jobs = 61849<br>
machines = 44<br>
transfer = 653<br>
" | |
|
| 5) | |
| | | Returns:
"p = 0.049181906279069584<br>
pow = 1.2383634763946774<br>
jobs = 399664<br>
machines = 71<br>
transfer = 408<br>
" | |
|
| 6) | |
| | | Returns:
"p = 0.018161592536226474<br>
pow = 0.6116683327948489<br>
jobs = 348579<br>
machines = 74<br>
transfer = 211<br>
" | |
|
| 7) | |
| | | Returns:
"p = 0.020518731031700967<br>
pow = 1.0120276148220704<br>
jobs = 275119<br>
machines = 24<br>
transfer = 904<br>
" | |
|
| 8) | |
| | | Returns:
"p = 0.03382227207890865<br>
pow = 1.6639976727243304<br>
jobs = 58645<br>
machines = 59<br>
transfer = 522<br>
" | |
|
| 9) | |
| | | Returns:
"p = 0.013639577518082074<br>
pow = 0.04280968978315358<br>
jobs = 31997<br>
machines = 11<br>
transfer = 80<br>
" | |
|