The ECN No Name Newsletter is no longer being published. This is an archived issue.

Running Large Jobs

As the end of the semester approaches, more and more people are running large background jobs as part of their research. Unfortunately, many people are unaware of the effects large jobs can have on the performance of the operating system. This article attempts to set forth some general guidelines and procedures which should be followed when running large jobs. If you have more specific questions not covered here, contact your Site Specialist. For the purposes of this article, a large process is defined as one which takes up more than one megabyte of memory. You can determine how much memory your program will take up by using the size program and looking at the number labeled ``dec''.

The main problem with large jobs is that they typically require more memory than the computer has physically connected to it and available for use. That you can execute programs like this at all is accomplished by the 4.3BSD UNIX operating system, which implements "virtual memory" . Virtual memory is accomplished by a sophisticated technique called paging . This technique, in essence, works by loading only a small part of your program into memory for execution, leaving the rest of it on disk. As your program moves through memory and accesses parts not in memory, the operating system will discard the parts in memory you are no longer using in order to make room for the new parts, which it loads in from the disk. Although the virtual memory system provided with 4.3BSD makes every effort to be as efficient as possible, it is still possible for a careless user to ``swamp'' the system, degrading performance both for himself and everyone else.

The most important rule to follow when running large jobs is to restrict yourself to no more than two at a time. The reason for this is simple, and can be explained by a somewhat oversimplified example. Consider a computer with 4 megabytes of main memory. With a load of about 35 users, this computer may be using 31/2 megabytes of memory, and will have 1/2 a megabyte free. If you start up two processes, each of which requires 3 megabytes of memory, the computer can only load in a small part of one of your programs before it runs out of memory. So, the computer will load in part of program one, execute it for a little while, and then switch to program two. But, since there is no free memory left, it must take program one out of memory in order to make room for program two. Thus, the computer is not only spending time executing your programs and everyone elses', but it is spending a great deal of its time ``shuffling'' things in and out of memory. Obviously, if you were to start up ten programs, each requiring 3 megabytes of memory, the computer would be spending more time moving things around to make room for each program than actually doing any useful work on your behalf. This is exactly what makes the computer seem to run so slowly at times - it has so many jobs to make room for, and so little memory to put them in, that it must spend more time moving programs in and out of memory than it can spend actually executing them. For this reason, we ask that you limit yourself to no more than two jobs at any given time if your program takes between 1 and 3 megabytes of memory. If your program requires more than 3 megabytes of memory, you should not run more than one job at a time. For those programs requiring more than 6 megabytes of memory, contact your site specialist to make special arrangements.

When working with large arrays of numbers (e.g., 1500 by 1500), it is important to understand how the arrays are stored in memory. By understanding this, you can make the optimum use of the virtual memory paging system. Generally speaking, it is best for the paging system if you can address your memory sequentially. That is to say, if you have an array of 100 numbers, it is best if you address the array as array [1], array [2], array [3], and so on, as opposed to array [56], array [10], array [37], array [91], etc. When using two-dimensional arrays, things become more complicated. In C, arrays are stored in ``row major'' order. This means that if you have an array of 25 rows by 50 columns, the first element of memory would be the first column in the first row of the array, the 52nd element of memory would be the second column of the second row, the 104th element of memory would be the fourth column of the third row, and so on. So, in C, it is best to move through a two-dimensional array as follows:

        int i, j;
        int array[ROWS][COLS];

        for (i=0; i < ROWS; i++)
                for (j=0; j < COLS; j++)
                        array[i][j] = ....

In FORTRAN however, arrays are stored in ``column major'' order. This means that if you have an array of 25 rows by 50 columns, the first element of memory would be the first column of the first row, the 52nd element of memory would be the third column of the second row, the 104th element of memory would be the fifth column of the fourth row, and so on. Unfortunately, this means that for optimum efficiency arrays must be accessed in a method which is different from the way we usually think:

        integer i, j
        integer array(ROWS,COLS)

        do 10 j = 1,COLS
                do 20 i = 1,ROWS
                        array(i,j) = ....
20      continue
10      continue

It should be noted that addressing arrays in this fashion is not a requirement, but if at all possible it should be done to improve efficiency.

Finally, some programs which use large amounts of data for relatively sequential calculations can be modified to use less memory. Consider as a simple example a program which must work on a 1024x1024 element (pixel) image. The program is to perform various smoothing operations on the data by computing the average of the eight elements surrounding each pixel. The easiest approach would be to simply read the entire image into memory. Unfortunately, if each pixel requires a 32-bit integer, the array will take up 4 megabytes of memory. An alternative to this approach would be to read in a small section of the picture at a time, process it, and then read in another section of the picture. For example, dividing the picture into quarters and processing each quarter individually (with some slight overlap in the areas) would require only one megabyte of memory. Because the program is smaller, the operating system will not have to page it in and out of memory as often, thus resulting in faster execution.

It unfortunately is often stated that by loading data entirely into memory, it can be processed more quickly. Although this is true under certain conditions, it is not the case when running large jobs on a time-sharing computer. Hopefully this article has provided you with some useful information which can increase your productivity, as well as decrease the load on the network machines as a whole.

HTML