The Faster, The Better

2001 Skadron Prize In Computational Physics

In a computer, each computational task is performed using a certain amount of memory space and taking a certain amount of time. When a multiple number of tasks are executed within a given amount of total memory space, how can we optimize a sequence of tasks so that the total execution time is shortest? This is a very challenging optimization problem.

To tackle this problem, we will use the following simple model, where each task is represented by a rectangle whose horizontal size corresponds to the memory space allotted to the task and whose vertical size corresponds to the execution time of the task. Our goal is to find a way of arranging many rectangles with different sizes into a container, whose width corresponds to the total memory size available in a computer, so that this arrangement gives the shortest overall height, which corresponds to the total execution time for all the tasks represented by the rectangles. It is therefore a sort of packing problem, which still turns out to be quite challenging.

Develop a subroutine that creates an arrangement of rectangles, whose horizontal and vertical sizes are given by the main program that will be provided by the department. The width of the container to which these rectangles are to be placed is also specified by the main program.

More Specifically

Write a FORTRAN subroutine ARRANGE.f that must start with the following 2 lines:

subroutine ARRANGE (MEM, ITIME, IM, IT, NTILE, MEMTOT)

dimension MEM(NTILE), ITIME(NTILE), IM(NTILE), IT(NTILE) where

MEM is an integer array variable whose size is NTILE, and MEM(I) represents the horizontal size of the I-th rectangle and is randomly chosen from a range between 1 and MEMMAX (MEMMAX < MEMTOT: the total memory size) by the main program;

ITIME is an integer array variable whose size is NTILE, and ITIME(I) represents the vertical size of the I-th rectangle and is randomly chosen from a range between 1 and ITMAX by the main program;

IM is an integer array variable whose size is NTILE and IM(I) represents the horizontal coordinate of the lower left corner of the I-th rectangle;

IT is an integer array variable whose size is NTILE and IT(I) represents the vertical coordinate of the lower left corner of the I-th rectangle;

For the contest, we will use the following values for NTILE, MEMTOT, MEMMAX, and ITMAX:

NTILE = 100, MEMTOT = 50, MEMMAX = 10, ITMAX = 10.

However, your subroutine should be able to run for any arbitrary values of these variables.

The Prize committee will run your subroutine ARRANGE with the main program which checks validity of the arrangement your subroutine creates and plots the arrangement. Your subroutine will be given three sets of rectangles and the main program calculates the average total height for the arrangements for these three sets. The first prize goes to the contestant whose subroutine gives the shortest average height. Your subroutine must also complete its computation for three sets of rectangles within 5 minutes.

CAUTION: do not attempt to examine every possible arrangement for the rectangles to find the one with the shortest height, simply because it will certainly take more than 5 minutes.

To test your subroutine ARRANGE.f:

1. To copy the main program "skmain.f" available on "entropy", type in:
   copy /u/hmb/skmain.f skmain.f
2. To compile your subroutine with the main program, type in:
   ncargf90 skmain.f ARRANGE.f
   
   "ncargf90" not only compiles the programs but also links the programs to NCAR graphics routines, which will allow us to plot each set of rectangles in the container.
3. To see the plots of three sets of rectangles, type in:
   ctrans -d t4105 gmeta
   
   After each plot, hit "return" on the keyboard to see the next plot.

Prizes

$300 ($ 200 for the winning team, $100 for the second best team).

Who can participate

Any Physics major at ISU.

Deadline

4 pm, April 30, 2001.