3
$\begingroup$

Horrible title, so let me explain - I think this must be a very basic statistical problem, but I don't remember what little statistics I once knew.

I'm writing a low-level emulator of an old IBM CPU. Each machine instruction of the IBM1620 was accomplished by a sequence of various "machine cycles". On the original machine, each cycle took exactly 20 microseconds. I'm emulating the various cycles with subroutines; they are much faster than 20 microseconds, and they do not all take the same amount of time to execute.

The 1620 had a magnificent light console that constantly showed the state of over 100 internal bits (data, registers, control switches) as the machine ran. I'm emulating that, too. Unlike the 1620, I can't manage to update my Java GUI 50000 times per second, as repainting after every 20 microsecond "cycle" would require. But I get a fine visual approximation simply by repainting the GUI every N cycles. [We can assume that repainting the GUI takes constant time.]

Without repainting the GUI at all, the emulator runs much too fast; repainting after every cycle makes it run much too slow. The graphical repainting is the ideal "friction" to apply to the emulator, to get it to approximate the true speed of the machine. The question is, what is N?

I have probes to count cycles and sample the system clock. The problem is that, due to several factors, the most important of which is that my emulations of the various "cycles" do not take equal time, the number of cycles in a measurement interval can vary a good deal, depending on the nature of the instructions the CPU was carrying out at that time.

I'd like, over time, to be able to converge on a "good" value of N, using some sort of method that can somewhat overlook anomalous readings. "Good"? "Anomalous"? I don't know how to define them. But if anyone can give guidance, even along the lines of "oh! you should check the Wikipedia article for The Backwards Freight Train Problem" [I'm making that up, of course], I'd appreciate it.

EDIT: to illustrate the problem, I'm appending some measurements. Here are a series of measurement intervals, each lasting 10000 cycles, showing:

  • interval time in microseconds (usecs),
  • the number of cycles executed between redrawing the updated GUI (cycs/redraw=51), currently constant,
  • the average GUI redraws per second (redraws/sec),
  • the cycles per second, expressed as a percentage of a real IBM1620, which was always exactly 50000 cycles per second.

And the question is: how might one vary cycs/redraw to bring Rate closer to 100%? Especially given that, as is obvious below, emulated cycles vary in duration.


CPU: Interval: Cycles=10000; usecs=174595; cycs/redraw= 51; redraws/sec:1123.  Rate:114%
CPU: Interval: Cycles=10000; usecs=197842; cycs/redraw= 51; redraws/sec: 991.  Rate:101%
CPU: Interval: Cycles=10000; usecs=179968; cycs/redraw= 51; redraws/sec:1089.  Rate:111%
CPU: Interval: Cycles=10000; usecs=157880; cycs/redraw= 51; redraws/sec:1241.  Rate:126%
CPU: Interval: Cycles=10000; usecs=151724; cycs/redraw= 51; redraws/sec:1292.  Rate:131%
CPU: Interval: Cycles=10000; usecs=150892; cycs/redraw= 51; redraws/sec:1299.  Rate:132%
CPU: Interval: Cycles=10000; usecs=151908; cycs/redraw= 51; redraws/sec:1290.  Rate:131%
CPU: Interval: Cycles=10000; usecs=172101; cycs/redraw= 51; redraws/sec:1139.  Rate:116%
CPU: Interval: Cycles=10000; usecs=159090; cycs/redraw= 51; redraws/sec:1232.  Rate:125%
CPU: Interval: Cycles=10000; usecs=165604; cycs/redraw= 51; redraws/sec:1184.  Rate:120%
CPU: Interval: Cycles=10000; usecs=135410; cycs/redraw= 51; redraws/sec:1448.  Rate:147%
CPU: Interval: Cycles=10000; usecs=130933; cycs/redraw= 51; redraws/sec:1497.  Rate:152%

$\endgroup$
2
  • 1
    $\begingroup$ Why can't you just pause every few cycles, check the system clock, and commence repainting once enough time has elapsed? (Or, more elegantly, run the repainting algorithm as a clock-triggered interrupt in the background.) What I'm really trying to discover is whether stats.stackexchange is the right place for this question: perhaps it belongs on one of the algorithms-oriented sites. $\endgroup$ – whuber Aug 8 '11 at 13:35
  • 1
    $\begingroup$ I understand your concern about whether this problem belongs on this site. I'm sure there are alternate algorithms I could try, but they require more elaborate programming and quite possibly introduce their own unknowns, such as task dispatching latencies. If I understood more stats, I might have been able to abstract the problem and not even mentioned computers. Perhaps what I'm asking is something along the line of "what is an average?" What I'm hoping for is that someone will be able to identify a generic statistical problem behind what I've described. $\endgroup$ – Chap Aug 8 '11 at 16:18
3
$\begingroup$

I'm going to offer a different answer, given the OP's comments. It would be inappropriate to spend much of your time learning regression in order to do this. Though I'd love for you to get something out of it, I feel it's better to put effort into the final project. :)

A much simpler method is to use what's known as a trimmed mean. If you have Excel, then the function is described at this page: http://office.microsoft.com/en-us/excel-help/trimmean-HP005209322.aspx.

In my regression answer, I assumed that each test would have a bunch of different instructions and you'd have access only to the final timing. If you are able to time each instruction separately, then the trimmed mean is the way to go. It will drop outliers, and you can specify what fraction to eliminate. For many cases, I frequently drop the outer 5%, i.e. trim at the 2.5%ile and 97.5%ile. It's good to look at those and see what's going on for the extreme values (e.g. optimizations or garbage collection), but I don't think you'll need to worry about it much.

Good luck!


(Update) I just realized that I didn't explain the trimmed mean. This is basically the mean of observations after the extreme values have been dropped (trimmed). There are other ways to get a robust estimate of the mean value, but this is probably the simplest. (The median is another robust estimator, but it's not always the same as the mean.) In any case, this gives you an estimate of the mean, disregarding some fraction of the extreme values, and that fraction is set by you.

$\endgroup$
3
  • $\begingroup$ Thanks - that sounds more like what I'm looking for. I think it should be possible for me to measure the relative execution speed of each of those 30-odd different "cycle" emulation subroutines. Will grant the checkmark when I've had a chance to learn about trimmed means, hopefully in OpenOffice. $\endgroup$ – Chap Aug 9 '11 at 2:30
  • $\begingroup$ Even if you don't call a trimmed mean function, you can get the same results by sorting the values and dropping (e.g. deleting) the tail rows. $\endgroup$ – Iterator Aug 9 '11 at 2:40
  • $\begingroup$ Thanks for note about trimmed mean. It seems to address the issue of "ignoring anomalous readings" in my original post. Thanks for your patience helping a stats neophyte express his problem -- suddenly, I'm finding statistical analysis intriguing! :-) $\endgroup$ – Chap Aug 9 '11 at 4:29
2
$\begingroup$

This may become very problematic in Java due to optimizations made by the JVM. Because subsequent runs may become faster due to optimizations or slower due to garbage collection, this might get weird.

Were you to go the statistical route, you could simply perform robust regression on the identifiers of the instructions called. For instance, suppose you have a 4 instruction vocabulary, IN1, ..., IN4. If you do many measurements (even better: well-designed experiments, but let's assume you're doing reasonable variation in the sampling), you can regress the total time on the counts for each of IN1, ..., IN4. Assuming no latency in execution, you may be able to set the intercept to 0. With rlm in the MASS package, you can do a robust regression on the predictors.

If this is for a demo for, say, a science museum, then the above answer may be adequate. If you are attempting to develop a new microprocessor, then I would really address the Java issues. It would be better to message when a light has changed and have a listener use that to update the screen; even better is to have it update just that section of the screen.

$\endgroup$
6
  • $\begingroup$ Good points about optimization and GC - at some point I will turn on some instrumentation to see what's going on in those departments. And, since it is for a science museum, the requirements for accuracy aren't terribly high. I don't know what "regression", "intercept", or "predictors" are, but I'll research on Wikipedia. Bottom line is I'm aiming for verisimilitude, both in run speed and in the "ripply, shimmering" appearance of the lights, which is improved by higher frame rates, and I'm hoping to dynamically determine a "sweet spot", keeping pace while maximizing shimmering! $\endgroup$ – Chap Aug 9 '11 at 1:52
  • $\begingroup$ I'm sure someone can help out with the R code if you provide a link. I suspect a lot of us owe some gratitude to science museums. :) By the way, if you want to maximize shimmering, you might look at the order of the lights. Rather than being slavishly faithful to the display, you can put the lights so that the most frequently blinking ones are spread out, or grouped in some ways. It isn't as informative to a real user as if the lights are ordered in terms of, say, entropy, but any interesting patterns in the lights could be very stimulating to kids. $\endgroup$ – Iterator Aug 9 '11 at 2:01
  • $\begingroup$ Any hint as to the location of the science museum? Btw, if IBM needs a place to house Watson, I have some space. ;-) $\endgroup$ – Iterator Aug 9 '11 at 2:09
  • $\begingroup$ If you're interested, go here: (jowsey.com/java/sim1620/ConsoleApplet1000.html). Flip on the Power switch, then press the Start button twice. This is an early version of what I'm working on :-) $\endgroup$ – Chap Aug 9 '11 at 2:11
  • $\begingroup$ The Computer History Museum page is (computerhistory.org/projects/ibm_1620). $\endgroup$ – Chap Aug 9 '11 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.