Having mis-read What course in CS deals with the study of RAM, CPU, Storage? I now wonder what course in CS deals with time and space complexities including GPUs, CPU caches in multiple levels, seek times on hard disk vs. SSDs, and bandwidth to disk and RAM.

I was taught the big O-notation but it never took into account that I might have a GPU with 100s of cores, or a limited amount of extremely fast cache, or a harddisk that is has a high bandwidth, but a high seek time.

Which class teaches this extended version of algorithm time complexities, which takes real world limitations into account?


I don't think these things are usually treated as a single topic in either research or education, but there are quite a few adjacent topics that are relevant. I'll list some here, starting with...


One perspective on the algorithmic analysis of computer storage, memory and caches is the field of I/O-complexity or external memory algorithms. These lecture notes from a course by Mark de Berg are a good introduction (in Part II). Note that this perspective assumes an abstract I/O model that has a two layer memory hierarchy (a small and fast internal memory and a big but slow external memory), which of course is a simplified version of what a modern computer has. Still, this perspective makes it possible to design efficient algorithms for dealing with massive data (think running an algorithm on an array/matrix a few ten GB big, or more!).

Another advantage of treating "external memory" only in the abstract means that we only need to design one algorithm to deal with both SSD's, hard-disks, or even a slow internet connection, as long as we are satisfied with treating our external memory as a monolithic blob. There are many other tricks you may want to try in practice, but this is highly dependent on your specific machine or operating system.

Operating Systems

Okay, but what if I really want to know how to use multiple cache layers, how to ensure seeking goes efficiently on my hard-disk, or how to play nice with my OS's paging? These topics (among others) are usually treated in a course called "Operating systems". Another aspect that frequently is the focus of such a course is concurrency (e.g. how does your OS manage to run all those processes "at the same time"? ), and dealing with multiple processes and threads programmatically. Some mild form of parallelism may also be covered.


So, what about those 100s of computing cores? Making use of those things to compute efficiently is known as parallelism and courses with that word in their title are common. There are quite a few models there to use in the analysis of parallel algorithms, the PRAM model is common. Again, this is an abstract model that may or may not allow you to use the full power of your expensive GPU (or arrays of relative cost-efficient Sony Playstation 3 cores. Cryptanalystist are a rare breed of "mostly theoretical" computer scientists that actually have use of massive computation power, see these slides of Dan Bernstein on some thoughts of using GPU's for crypto).

However, unless you have a very extreme needs for high performance computing, "using GPUs" in practice usually means using one of the APIs/frameworks designed to use them, like OpenGL. There are courses called computer graphics or something similar that teach how to work with these APIs.

Speaking of high performance computing, this is a field of its own, a bit on the intersection of parallel and distributed computing. (see also this answer for the difference between distributed computing, concurrency, and parallelism)

I should also mention that there are also courses on databases that go beyond just teaching how to use them and also teach how all those operations are implemented efficiently.

But nobody will teach you this one simple trick!

We've already covered quite some courses, certainly enough to fill a few semesters, but you may have already gathered from the multiple caveats above that there's always a manner of tricks that simply depend too much on the specifics of your setup that there's no good reason to teach it, or do theoretical research on. Still, having the knowledge of the courses above at least should give you a good idea on when it might be a good idea to depend on some strange trick, or whether there actually is a well-understood way to solve your problem. One interesting trick is to compress everything and make it fit in main memory. (see also the video explaining how their entire system works)

| cite | improve this answer | |

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.