We have developed a sequential approach which predicts the time that a computer
algorithm will take to solve a large problem of specified size on
a given system. We use regression
techniques to extrapolate observations of the time needed to solve smaller
problems. The past observations and current predictions are used to
adaptively decide the size of problem to be observed next.
While based on classic ideas, some unique aspects occur in this
setting. One is that observations of small inputs can be accomplished more
quickly than observations for larger inputs, which raises interesting design
optimization questions when one has a fixed amount of time in which to generate
the prediction. Another is the change-point phenomena as one moves from a
working set in cache to one in RAM (and perhaps even one larger than the RAM
available).
Our measurements have also uncovered some interesting behavior of
the computing systems.
Keywords:
adaptive sampling, computer performance prediction, benchmarking,
learning theory,
experimental algorithms, design of experiments, change-point, model checking,
computer science, statistics
