Memory-limited workloads

Question

I'm trying to figure out whether computing workloads, particularly those related to science and engineering, have historically been limited by memory or CPU. (By the former, I mean not memory access speed, but memory amount; even if it takes multiple clock cycles to access RAM, that's still orders of magnitude faster than having to go to disk.)

In theory, CPU speed has increased only slightly faster than memory amount over the decades, from 8-bit computers with kilobytes of memory and maybe a kiloflop of CPU, to modern computers with gigabytes of memory and gigaflops to teraflops. Many science and engineering workloads use algorithms significantly superlinear in problem size, so from that perspective one would expect a transition from memory-limited early on to CPU-limited later.

Anecdotally, my experience supports that; in the old days, CPU speed was actually not important because you would always run out of memory first, but in more recent years you sometimes get to wait for the CPU. But there are many workloads with which I have no experience.

So: is it actually true that workloads prior to recent years were often limited by memory rather than CPU? I would be interested in anything from other people's anecdotal experiences, to references to scientific workloads running out of memory, efforts put into obtaining more memory, or ideally if anyone has actually run a full study on this question.

Answer 1

Naïve programming was often limited by memory speed even for the fastest mainframes available in the 1980s. For example on an IBM S/370 system, the maximum amount of memory available to a single user program could be limited to about 9MB out of an address space of 16MB (the other 7 being reserved for the operating system!) compared with hundreds of MB of disk, or an effectively unlimited amount of data on tape.

The solution was not to write naïve programs. The basic techniques were exactly the same as those now used, at a different scale, to avoid "cache misses" etc - for example to organize the data storage so that the maximum number of CPU operations could be done on a subset of the data, before exchanging it for the next subset.

Sometimes, the computer operators who did the tape-swapping were on the critical path for computational efficiency. I remember a benchmark being run by Cray Research for an oil exploration company. The company asked if they could provide their own tape operator, who was familiar with their tape volume labelling systems, etc, which was agreed. On the benchmarking day, the visitors arrived, installed their software, and checked it out on a small problem. The Cray guys then asked them "so, where are your tapes for the benchmark?" The answer was "In the 20-ton truck that's in your visitors' car-park - can we move it a bit closer to the machine room, please?" A one-hour benchmark run needed over 100 manual tape changes! Rather than risk forgetting a critical tape reel , they had just brought their entire tape library with them.

Answer 2

Memory hasn't always been the limitation. IBM identified (and in many ways, encouraged the adoption of) two kinds of computing: scientific and data processing. Data processing computers (such as the IBM 702 from 1953) had relatively modest processor power, but enough memory to hold all the parameters for the day's business transactions to ensure that processing could be finished before the next day's work was needed. Compare this to the scientific machines (such as 1954's 704) that had tiny amounts of memory but could crunch floating point numbers quickly for numerical analysis. IBM's business and scientific machines ran completely different instruction sets, and evolved into two completely separate computer cultures.

Since you asked for anecdotes, my father was once (briefly) accused of breaking a utility's billing mainframe. Dad was an analyst for ICT in the early 1960s, and his team was asked to spec and write a network flow analysis for the Scottish Gas Board's pipes. The data (which would likely fit on a single screen of spreadsheet today) was too big to analyze in any of ICT's scientific machines, so they had to write it for the utility's billing computer. Even with the “large” (a few kilo-words) amount of memory in the billing machine, the task had to be broken into many processing chunks, with each chunk dumping its data and chaining in the next task. The main analysis chunk was estimated to just fit in the processing time that the Billing Department had grudgingly allowed the pipeline boffins on the commercial machine.

You may not remember, but in the days of mag tape drives (✇✇), computer data processing activity correlated with the tapes spinning now and again. Each data record was read, processed and written, and the tapes advanced a bit every time. A working computer had mag tapes that moved; everyone knew that. Even poets knew it: Brautigan wrote of a techno-pastoral utopia “where deer stroll peacefully / past computers / as if they were flowers / with spinning blossoms”. So spinning tapes = working computer = happy operator.

Dad's network analysis job had to be run at an unpleasant hour of the night, after the day's billing had been run but before the next morning's readings started to come in. The job got set up, and the accounting operator approved of the first stages: the tapes kept moving, so the computer was working.

Then came the main analysis. Once the tape drives had loaded all the data into core, the slow processor in the accounts machine started its work. The tapes stopped … and stayed stopped. After a couple of minutes, the operator started to fret, asking if it was supposed to do this. Despite positive assurances, his fretting increased as the minutes ticked by with no tape activity. Apparently the operator was almost screaming, threatening to have my dad escorted from the building and his company billed for the whole computer that they'd “broken”, when a tape moved! The results spooled to tape from core, and the operator calmed down a bit (as did my dad, who was apparently beginning to have doubts of his own.) I don't know how long the job took to run — probably less than half an hour — but it certainly pushed that computer operator's experience well out of the comfort zone.

Personally, I've also experienced processor limitations (making Julia Set animations on an Amiga A500 in the early 1990s, the first time I had to let a computer run all night) and I/O bandwidth bottlenecks (ripping > 1000 CDs on two computers and four CD-ROM drives: it took a couple of weeks). But none have resulted in threats, so far at least.

Answer 3

As you suggest, you always ran out of memory before you ran out of processing power.

In the 1980s and into the 90s, memory was significantly more expensive. Not only in absolute terms but also in relative terms to CPU prices. Even hard drives were pricey. I remember the first hard drive I bought for a microcomputer cost me £7,000 for a massive 5Mb - that was 1983 or 1984.

Pretty much all the applications I was involved in writing in that time were heavily memory constrained. For example, I wrote a compiler for the PDP-11 in 1987 that used memory overlays to page each pass of the compiler into memory in turn, while keeping just a supervisory package in memory continuously. Running a compilation could take a couple of hours.

The company I worked for at the time explored the possibility of buying a Quantel Paintbox to do some image analysis. This was based upon a PDP-11 with multiple parallel framestores. This beast had more RAM than I had ever seen before but the cost was far beyond the company's budget. However, I managed to get a system working to meet the requirements on a BBC Micro. This put the software in Sideways ROMs that shared the load in order to keep the image data in RAM.

So, you asked for anecdotal evidence, in my experience we were always memory constrained.

Answer 4

In the data compression domain, the Burrows-Wheeler transform was invented in 1983, but kept unpublished until 1994, likely because of its memory requirements. Without at least several Mb of RAM, it is a mere curiosity, its usefulness as a compression algorithm cannot be demonstrated.

To achieve a compression rate comparable to that of a competing algorithm, e.g. ZIP, the buffer size for the BWT should be of the order of hundreds of kilobytes, and the supporting data structures require at least one integer per byte. The algorithm involves sorting, therefore the whole data segment must be in RAM to avoid thrashing.

Answer 5

And I just serendipitously stumbled across a discussion thread at https://news.ycombinator.com/item?id=14243303 with some relevant anecdotes.

... had a Quadra 950 with 128MB of RAM, which required some pretty exotic SIMMs. That would be a pretty expensive machine in today's money. This was for handling Adobe Illustrator files with large embedded images.

Designers that did print-quality photography, especially posters, have always been crying out for more memory.

I worked at a Forestrey Commission Research Station here in the UK in the 90s. One of the mathematicians was running an environmental model on a Sun workstation and it was running out of RAM and swapping and was going to take 2 days to run at that rate...

I blew a thousand dollars (Canadian) to upgrade my new Mac Plus to 4 megabytes and the sales guy asked --slightly tongue in cheek but only slightly-- if I was doing CAD for NASA.

Answer 6

I'm trying to figure out whether computing workloads, particularly those related to science and engineering, have historically been limited by memory or CPU.

Computing workloads limited in what aspect?

• I'm going to assume you mean limited in accuracy, and limited in speed, since any other type of limitation is going to prevent the workload from running at all.

Large simulations are today very much dependent upon wired RAM. At my place of work, many types of physics and electronics simulations take "as much RAM as you can fit on the board". I frequently see applications that demand up to 64 GB per simulation thread; with others recommending 512 GB for faster processing.

The common thread for both RAM-limited accuracy and RAM-limited speed, across multiple different types of simulation, is recursion; and this isn't even a historical hypothetical situation.

Typically, the underlying algorithms are massively recursive. The limits of available RAM place a limit on the depth of recursion.

The same is true of historical computing, since the science isn't new, and the algorithms working on those models have not changed much, except in the depth of recursion available.