JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: AMD Multicore Threadfest 1
Problem: ProcessorScheduling

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)
    
p = 0.02945198102051495
pow = 0.7984954674161717
jobs = 217212
machines = 84
transfer = 307
1)
    
p = 0.022017740201681367
pow = 0.0512270939535211
jobs = 28793
machines = 52
transfer = 193
2)
    
p = 0.04084870687857926
pow = 0.23936634704587667
jobs = 284560
machines = 20
transfer = 581
3)
    
p = 0.043578829942208575
pow = 0.3477121219273487
jobs = 299706
machines = 77
transfer = 919
4)
    
p = 0.021666605038956104
pow = 0.09719726359971026
jobs = 61849
machines = 44
transfer = 653
5)
    
p = 0.049181906279069584
pow = 1.2383634763946774
jobs = 399664
machines = 71
transfer = 408
6)
    
p = 0.018161592536226474
pow = 0.6116683327948489
jobs = 348579
machines = 74
transfer = 211
7)
    
p = 0.020518731031700967
pow = 1.0120276148220704
jobs = 275119
machines = 24
transfer = 904
8)
    
p = 0.03382227207890865
pow = 1.6639976727243304
jobs = 58645
machines = 59
transfer = 522
9)
    
p = 0.013639577518082074
pow = 0.04280968978315358
jobs = 31997
machines = 11
transfer = 80

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.