Scaling is a term that is sometimes overused. It can apply to how many applications a computer can execute simultaneously, how many disks can be written to simultaneously, or how many cream cheese bagel orders can be processed by the local bagel shop’s crew. When the output cannot be increased no matter how many resources are added, this limit is generally the value used to specify what something scales to. If the oven cannot produce more bagels per hour, it does not matter how many people are added to the assembly line: the rate of bagels cannot exceed the rate produced by the oven. The scaling limit can also be controlled by many other factors, such as the rate that the cream cheese can be produced, the size of the refrigerators, or even by the suppliers for the bagel shop.

In this chapter, when we refer to the scalability of a multithreaded application, we are referring to the limit on the number of processors we can add and still obtain an acceleration. Adding more than this limit will not make the application run faster. Obviously, how an application scales depends on many factors: the operating system, the Java virtual machine implementation, the browser or application server, and the Java application itself. The best an application can scale will be based on the scalability limits of all of these factors.

For perfect CPU-bound programs in a perfect world, we could expect perfect scaling: adding a second CPU would halve the amount of time that it takes the program to run, adding another CPU would reduce the time by another third, and so on. Even for the loop-based programs we’ve examined in this chapter, however, the amount of scaling that we will see is also limited by these important constraints:

If we view the setup time, synchronization time, and time required to execute the serialized methods as a percentage of the total running time, the remaining time is the amount of code that is parallelized. The maximum amount of scaling that we’ll see is given by Amdahl’s law:

Here, S is the scaling we’ll see, assuming that F % of code is parallelized over N processors. If 95% of the code is parallelized and we have eight processors available, the code will run in 16.8% of the original time required (.05 + .95/8). However, when we introduce code to calculate loop ranges (or any other code), we’ve actually increased the amount of serialized code, so F could potentially be a negative number. In that case, our parallelized code will take longer to run than our original code.

So what sort of scaling can we expect from the techniques of this chapter? In order to answer this question, we will test several implementations of our sample double loop:

public float[][] getValues() {
    for (int i = 0; i < 360; i++) {
        lookupValues[0][i] = 0;
    }
    for (int j = 1; j < 1000; j++) {
        for (int i = 0; i < 360; i++) {
            float sinValue = (float)Math.sin((i % 360)*Math.PI/180.0);
            lookupValues[j][i] = sinValue * (float)i / 180.0f;
            lookupValues[j][i] += lookupValues[j-1][i]*(float)j/180.0f;
        }  
    }
    return lookupValues;
}

To make testing easier, we will use the following class and interface to build a system by which we may test various loop handlers. Since we’re working with CPU-intensive threads, we’ve included the Solaris-specific code to set the number of LWPs, but this code will run on any operating system:

public interface ScaleTester {
    public void init(int nRows, int nCols, int nThreads);
    public float[][] doCalc();
}

import java.util.*;
import java.text.*;
import java.io.*;

public class ScaleTest {
    private int nIter = 200;
    private int nRows = 2000;
    private int nCols = 200;
    private int nThreads = 8;
    Class target;

    ScaleTest(int nIter, int nRows, int nCols, int nThreads,
                String className) {
        this.nIter = nIter;
        this.nRows = nRows;
        this.nCols = nCols;
        this.nThreads = nThreads;
        try {
            target = Class.forName(className);
        } catch (ClassNotFoundException cnfe) {
            System.out.println(cnfe);
            System.exit(-1);
        }
    }

    void chart() {
        long sumTime = 0;
        long startLoop = System.currentTimeMillis();
        try {
            ScaleTester st = (ScaleTester) target.newInstance();
            for (int i = 0; i < nIter; i++) {
                st.init(nRows, nCols, nThreads);
                long then = System.currentTimeMillis();
                float ans[][] = st.doCalc();
                long now = System.currentTimeMillis();
                sumTime += (now - then);
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
        long endLoop = System.currentTimeMillis();
        long calcTime = endLoop - startLoop;
        System.err.println("Loop time " + sumTime +
                            " (" + ((sumTime * 100) / calcTime) + "%)");
        System.err.println("Calculation time  " + calcTime);
    }

    public static void main(String args[]) {
        if (args.length != 5) {
            System.out.println(
    "Usage: java ScaleTester nIter nRows nCols nThreads className");
            System.exit(-1);
        }
        ScaleTest sc = new ScaleTest(Integer.parseInt(args[0]),
                                     Integer.parseInt(args[1]),
                                     Integer.parseInt(args[2]),
                                     Integer.parseInt(args[3]),
                                     args[4]);
        CPUSupport.setConcurrency(Integer.parseInt(args[3]) + 5);
        sc.chart();
    }
}

When we use the ScaleTest class, we get two numbers: the number of milliseconds required to run the entire program (including initialization, which is single-threaded) and the number of milliseconds required to run just the loop calculation. We can then compare these numbers to determine the scalability of various implementations of our loop handling classes.

As a baseline, we’ll take the measurement of this class:

public class Basic implements ScaleTester {
    private float lookupValues[][];
    int nCols, nRows;

    public void init(int nRows, int nCols, int nThreads) {
        this.nCols = nCols;
        this.nRows = nRows;
        lookupValues = new float[nRows][];
        for (int j = 0; j < nRows; j++) {
            lookupValues[j] = new float[nCols];
        }
    }

    public float[][] doCalc() {
        for (int i = 0; i < nCols; i++) {
            lookupValues[0][i] = 0;
        }
        for (int j = 1; j < nRows; j++) {
            for (int i = 0; i < nCols; i++) {
                float sinValue =
                                (float)Math.sin((i % 360)*Math.PI/180.0);
                lookupValues[j][i] = sinValue * (float)i / 180.0f;
                lookupValues[j][i] +=
                                lookupValues[j-1][i]*(float)j/180.0f;
            }
        }
        return lookupValues;
    }
}

This class contains no threading; it is the way that we would normally implement the basic calculation we’re interested in testing. One of the implementations that we’ll compare this class against is the following loop handler class:

public class GuidedLoopInterchanged implements ScaleTester {
    private float lookupValues[][];
    private int nRows, nCols, nThreads;

    private class GuidedLoopInterchangedHandler
                                    extends GuidedLoopHandler {
        GuidedLoopInterchangedHandler(int nc, int nt) {
            super(0, nc, 10, nt);
        }

        public void loopDoRange(int start, int end) {
            for (int i = start; i < end; i++) {
                lookupValues[0][i] = 0;
            }
            for (int i = start; i < end; i++) {
                for (int j = 1; j < nRows; j++) {
                    float sinValue =
                                (float)Math.sin((i % 360)*Math.PI/180.0);
                    lookupValues[j][i] = sinValue * (float)i / 180.0f;
                    lookupValues[j][i] +=
                                lookupValues[j-1][i]*(float)j/180.0f;
                }  
            }
        }
    }

    public void init(int nRows, int nCols, int nThreads) {
        this.nRows = nRows;
        this.nCols = nCols;
        this.nThreads = nThreads;
        lookupValues = new float[nRows][];
        for (int j = 0; j < nRows; j++) {
            lookupValues[j] = new float[nCols];
        }
    }

    public float[][] doCalc() {
        GuidedLoopInterchangedHandler loop =
                    new GuidedLoopInterchangedHandler(nCols, nThreads);
        loop.loopProcess();
        return lookupValues;
    }
}

This class uses our simple loop handler to process the loop; notice, however, that we’ve interchanged the loops in order to make the outer loop threadable.

Table 9.1 lists the results of the ScaleTest program when run with different implementations of the interchanged loop: we’ve used chunk, self-scheduled, and guided self-scheduling loop handlers in conjunction with the code we showed earlier. These tests were run on a machine with eight CPUs, using an iteration count of 200. We’ve normalized the running time for the baseline run to be 100 so that other numbers can be viewed as a percentage: the best that we do is run in 20.6% of the time required for the original run. The first number in each cell represents a run with 500 rows and 1000 columns, and the second number represents a run with 1000 rows and 500 columns.

There are a few conclusions that we can draw from this table:

All in all, though, we’ve achieved very good scalability.

What effect does a storeback variable have in our testing? We can rewrite our tests so that every time we calculate a lookup value, we add that value to a sumValue instance variable. Using the reduction technique we showed earlier, the modified test generates the numbers given in Table 9.2.

Because there’s only one storeback variable, the effect on the scaling is minor. In fact, in some cases we did better because the baseline now takes longer to execute. However, the effect of many storeback variables could potentially aggregate into something more noticeable.

What if we had threaded only the inner loop? This question is very interesting, since it demonstrates the effect of synchronization overhead versus the amount of savings we obtain if the inner loop is small. Rewriting our first test (with no storeback variable) so that no loop interchange is performed and the inner loop is threaded instead produces the results in Table 9.3.

So what has happened here? First, we’ve slightly modified our test parameters: the first number was produced with a run of 100 rows and 5000 columns, and the second number was produced with a run of 500 rows and 1000 columns. In the first case, we’ve achieved some scalability to a point of four CPUs, which allows us to run inner loops of about 250 calculations per CPU. By the time we get to eight CPUs, however, the inner loop has only 125 calculations, and the additional overhead of repeatedly calling the synchronized loopGetRange() method has overcome any advantage we received by running the small loops in parallel. Things get drastically worse as we add additional threads.

In the second case, the inner loop is so small that we end up calling the loopGet-Range() method so many times that there is never any scalability. In the best case (with two threads), we’ve added the equivalent of 43% more code than we’ve parallelized.

As we mentioned, threading of small loops—and particularly of small inner loops—is not necessarily worthwhile.

Finally, what if we add code to the loop that prints out the result of some calculations? We can still thread such a case using the LoopPrinter class that we developed earlier. However, remember that we ended our section on the LoopPrinter class with a discussion that would enable us to remove the synchronization from the LoopPrinter class. Because in this particular test we always know the size of the output array and we can ensure that the same index is not used by two different threads, we can rewrite the LoopPrinter class like this:

import java.util.*;
import java.io.*;

// Non-thread-safe version of a loop printer
public class LoopPrinter {
    private Vector pStorage[];

    public LoopPrinter(int size) {
        pStorage = new Vector[size];
    }

    public void print(int index, Object obj) {
        if (pStorage[index] == null) {
            pStorage[index] = new Vector();
        }
        pStorage[index].addElement(obj.toString());
    }

    public void println(int index, Object obj) {
        print(index, obj);
        print(index, "
");
    }

    public void send2stream(PrintStream ps) {
        for (int i = 0; i < pStorage.length; i++) {
            if (pStorage[i] != null) {
                Enumeration e = pStorage[i].elements();
                while (e.hasMoreElements()) {
                    ps.print(e.nextElement());
                }
            }
        }
    }
}

With this new version of the loop printer, there is no longer any synchronized code, and hence it should have fewer problems scaling. However, with all the calls to the Vector class, even this version of our loop printer adds a significant amount of overhead to our multithreaded program. In addition, it still takes longer to add strings to these vectors and then dump them out than to simply call the System.out.println() method. However, the difference between our thread-safe and our thread-unsafe versions of this class is important. Table 9.4 lists the results that we obtained for both cases.

The first set of numbers in this table results from running 200 iterations with 200 rows and 1000 columns and printing out every 100th row. The second set of results shows what happens when we print out every 20th row instead. By the time that we print out every 20th row, the amount of extra code prevents any reasonable scaling at all. This is clearly a case where careful design and use of an unsynchronized class can have a big benefit.

We realize that this technique is at odds with our previous admonishments to produce thread-safe code. We still recommend that you always start with threadsafe code. In cases like this, however, when you take the extra care necessary to ensure that you use the thread-unsafe code correctly, the scaling benefits may outweigh the extra effort required to code carefully enough to prevent any race conditions.