Sunday, January 1, 2017

Wednesday, November 30, 2016

Measure Twice, Cut Once

In a previous post, I observed that, as I increased the number of cores in my GPGPU, performance began to plateau and hardware threads spent more time stalled because their store queue was full. I speculated that the latter might cause the latter, although that wasn't definitive. The current implementation only has a single store queue entry for each thread. One optimization I've been considering is adding more store queue entries, but this has subtle and complex design tradeoffs.

Sunday, September 4, 2016

Further Reading

A passage from Mortimer J. Adler and Charles Van Doren's "How to Read a Book," discusses reading for understanding:
"If the book is completely intelligible to you from start to finish, then the author and you are as two minds in the same mold. The symbols on the page merely express common understanding you had before you met.
Let us take our second alternative. You do not understand the book perfectly. Let us even assume--what unhappily is not always true--that you understand enough to know that you do not understand it all. You know the book has more to say than you understand and hence it contains something that can increase your understanding... 
Without external help of any sort, you go to work on the book. With nothing but the power of your own mind, you operate on the symbols before you in such a way that you gradually lift yourself from a state of understanding less to one of understanding more. Such elevation, accomplished by the mind working on a book, is highly skilled reading, the kind of reading that a book which challenges your understanding deserves"

Sunday, July 24, 2016

GPLGPU Walkthrough

A few years ago, an interesting kickstarter projected popped up:

https://www.kickstarter.com/projects/725991125/open-source-graphics-processor-gpu

The goal was to publish source code to a GPU that is register compatible with the late 90's era Number Nine "Ticket To Ride IV" GPU. Although the project didn't meet its funding goal, the person behind it later published the code on github.

https://github.com/asicguy/gplgpu

Although this is an older design, it has a lots that is worth studying. It's instructive to compare it to the VideoCore GPU that I walked through in a previous post. While there are some fundamental differences, there are surprising number of similarities, which shows how modern GPUs evolved from earlier ones.

Tuesday, March 1, 2016

VideoCore QPU Pipeline

As a followup to the last post, I've taken a closer look at the Quad Processor Unit that executes shaders on the VideoCore GPU. Although it superficially looks like a CPU, there are some important fundamental differences, and the reasons for them are interesting.

Friday, February 26, 2016

Life of a Triangle

A few years ago, Broadcom released full specifications for their VideoCore IV GPU, which is in the system-on-chip on the popular Raspberry Pi dev board. Before this, most details of commercial GPUs were secret. Although GPU manufacturers released white papers and some academic publications, they were often greatly simplified and lacked important details.

Tuesday, November 3, 2015

Lost in Translation

I sometimes sympathize with Mike Mulligan, staring up from the bottom of his freshly dug basement at four neat walls and four neat corners and realizing he's forgotten to leave a way out. The advantage of construction in the virtual world is that it's easy to back up and start over. Sometimes my approach to a complex new feature is to implement until I run into a dead end, revert my changes, and think about it some more. It's not uncommon for me to make several runs at a feature, each time building a better mental model of the problem.

Thursday, June 11, 2015

Quake Lightmaps

I added support for lightmaps to the Quake renderer I discussed in the last post.  Lightmaps were a big innovation when they first appeared in Quake. By precalculating light and shadow, they allowed much more realistic scenes than would have been possible to compute in realtime. Lightmaps are still used in many games.

Friday, June 5, 2015

Not so fast

I wrote a custom engine to render Quake levels with my GPGPU. After fixing many subtle hardware lockups and compiler backend gremlins, I'm right chuffed to see this running reliably on an FPGA. It stresses a lot of functionality: hardware multithreading, heavy floating point math, and complex data structure accesses.

I won't be challenging anyone to a deathmatch any time soon

But... it's running at around 1 frame per second. While this is only a single core running at 50 Mhz, the original Quake with a software renderer ran fine on a 75 Mhz Pentium, so there's a lot of room for improvement. I'll dig more into the performance in a bit, but first, some background on how this works.

Tuesday, April 14, 2015

The Mystery of the Missing Pixels

One goal when I started my GPGPU project was to be able to display 3D graphics with my FPGA board on a VGA monitor. This required me to add an SDRAM controller, since there is not enough block SRAM on the FPGA to contain an entire VGA framebuffer. I managed to execute code running out of SDRAM on the processor, and display static images on the monitor. But, to my dismay, when I tried to render animations in real time, the monitor displayed garbage. I imagined all kinds of gnarly data corruption bugs that could exist in the SDRAM controller. Stepping through millions of memory transactions to find the problem was enough to make me want to go back to writing software.

Saturday, March 21, 2015

Booting

Most things don't start out complicated. In fact, paradoxically, sometimes the things that start the simplest end up accumulating the most complexity over time. The process of loading code onto the FPGA version of the GPGPU I've been working on has become kind of messy, and I've been considering how to clean it up. The challenge with a project like this is that it highly unconstrained. Much like deciding what to have for dinner, the number of choices can be overwhelming. However, simplicity and ease of setup are a high priority for me, so that's at least a useful guiding criterion.

Saturday, February 28, 2015

Automatic Cache Prefetching


Many optimizations take the form of "lazy evaluation."  When an operation may end up not being needed, we defer it as long as possible for the chance of avoiding it entirely. However, there is another class of optimizations which attempt to do work speculatively before we know that we need to. At first blush, it seems like there are a few conditions where it might be advantageous to do this:

 1. If the operation has a lot of latency.
 2. If the resource that is needed for the operation tends to be underutilized.
 3. The operation ends up being needed most of the time anyway.

I've experimented with automatically prefetching cache lines to improve performance in my GPGPU design. This is a common technique in many computer architectures. When a cache miss occurs, it will automatically read a few of following cache lines.

Saturday, February 21, 2015

Improved 3D engine profile

I reworked the 3D renderer recently, improving performance and adding features to make it more general purpose.  This included improved bin assignment to reduce overhead, tracking state transitions properly, and adding features like clipping.

Sunday, December 21, 2014

Mip-Mapping

I added mipmapping support to the software renderer for my GPGPU project.

Saturday, December 6, 2014

Branch Divergence

Modern GPUs utilize SIMD heavily (under various monikers: SPMD, SIMT, etc).  Whatever the name, it fundamentally boils down to duplicating arithmetic units and applying the same instruction to many vector lanes, each of which represents an independent instance of the program. Because the non-arithmetic parts of the pipeline are shared, this allows packing more computation in a smaller amount of space.

This works well until conditional execution is thrown into the mix.  It's possible (common, actually) that some of the instances will chose one branch and some will chose another.  This is called "branch divergence," and is an active area of research. I've recently written a compiler for a simple, C-like language that can produce parallel kernels for the instruction set of the processor I've been working on. It uses the LLVM backend I've already developed for this architecture. It's interesting to compare the generated code to a modern GPU, AMD's "Southern Islands" architecture.

Monday, December 1, 2014

Doom

How many instructions does a processor need to execute to get through the first level of Doom?  About 2.7 billion, in my case.  Over the course of the several minutes it took me to stumble through the level, it rendered about 1080 frames, each of which required about 2.5 million instructions to produce. The other 700 million instructions initialized the game, loading textures, setting up data structures, etc. 

Thursday, August 21, 2014

"It works in the simulator..."

I do most hardware development in simulation. It allows a level of visibility that software developers can only dream of: I can see the state of every signal at every instant for the entire run. But there is a dark side to simulation: the synthesized design may not behave the same as the simulation. There are a few well known patterns that lead to synthesis/simulation mismatches that are easy enough to avoid with attentive coding, but the existence of these gremlins always leaves me uneasy...

Saturday, July 5, 2014

Write-back vs. write through bake-off

In the last update, I was debating whether the complexity of a write-back cache was justified by the performance increase. I ran a little bake-off between the version 1 microarchitecture, which uses a write through L1 cache, and the in-progress version 2 using a write-back L1 cache. There are many other differences between the architectures which would affect performance, but I'm going to focus on memory access patterns, which should be similar.  I used the same teapot benchmark as in previous posts, as it has a nice mix of memory accesses. Both versions are running one core, so there are aspects of cache coherence traffic that aren't captured, but I'll get to that in a minute.

Friday, July 4, 2014

Messy Details

A problem with books and papers about computer architecture is that they gloss over messy details. The block diagram looks so simple, but, when you begin to implement it, you realize there are fundamental structural hazards. They give no hints about how to handle them. Often, a subtle detail completely alters the design. I'm going to talk about a lot of details around the cache hierarchy, specifically the way the L1 and L2 caches communicate with each other, and a design design with the current microarchitecture I am implementing.

Friday, June 6, 2014

Faster than light

In the last post, I discussed the fastest possible execution time of a test program, the "speed of light," as it were. There was an important assumption in this calculation: that the CPU issued one instruction per cycle. A common technique to improve performance in modern processors is issuing multiple instructions in the same cycle, also known as superscalar. I hadn't put much thought into a superscalar design given the focus on utilizing the wide vector unit. However, some helpful comments in a previous post have led me to reconsider this decision.