BatWerk 3 - Pains

The goal of the BatWerk exercise app (Android / iOS) is to keep you healthy, happy and productive without requiring you to overhaul your life. This is a series of blog posts that talks about the different aspects of an exercise app and how we're approaching them in BatWerk (Intro, How do muscles work, Pains, Maintaining the routine, How to play). Interested? How would you like to improve it?

Where does the pain come from? You know. The one that you get from wearing headphones all day. Or the one from sitting at your desk tapping away at the secrets of the universe. Or that one where you're thumbing your mobile for hours on end.

Pain

The initial thoughts I had around pain: Pain is a bunch of nerves firing pain signals and those getting carried up to the brain. Painkillers block the inflammation response without fixing the root cause. The nerves fire pain signals because they're activated in some way. Maybe there's something pressing on the nerve, maybe the nerve is under tension, maybe there's damage of some sort that's causing the nerve to fire. 

Going from there, what could be pressing on the nerve? Holding your body in a painful position. Build-up of liquid that increases pressure on the nerve. Inflammation. Damage to the nerve.

Some causes are difficult to fix by yourself, but some are more feasible. Painful position? Change position. Find a good sleeping position. Static load on muscle that causes build-up of liquid (e.g. using a computer / phone for a few hours)? Take regular breaks, try to unlock the muscle by locating it with status query meditation, massage, and 10-15 minutes of varied moves. Throw in a painkiller to help reduce the inflammation. Wearing headphones and getting neck pain? Try earbuds. Pain on the sides of your head? Bring your display down so that you don't have to look up so much. 

Wrists hurting after a day at the keyboard? Wear mittens. Set a timer to lock the screen every 15 minutes. Do pushups, curls and grips to strengthen your wrists and fingers. Move your fingers less when typing. Use a flat keyboard with minimal force required.

Prevention design

Doing the micro-exercises every half an hour over the work day has been a pretty good preventive measure. It makes me move often enough and with enough variety that I don't get as many static load lockups. Still happens sometimes though, especially when I zone into something for more than an hour, or keep working in a weird position for a while. The workout and the neck stretch set can help there but it's kind of tough to get yourself through 15 minutes of movement when your head is splitting and you just want to sleep.

What sometimes helps is the painkiller, movement and massage -combo. Block the pain to loosen up the muscle, then wash the dishes to shake them more, find out which neck muscle is hurting and massage that. It usually gets me far enough that I can fall asleep and rely on the sleep relaxation to fix stuff up.

The BatWerk moves contain a bunch of neck motions and core moves, twists and stretches because a major goal for the app is to act as a preventive painkiller. If your body doesn't lock up, it's not going to get lock up pains, right? Would love to make it even better, so let me know if you can help.

Deep pain

What we have above are high level features of sedentary office worker pain. Folk medicine. But what is actually happening on a deeper level when your wrist starts to hurt?

Okay, so, let's say that you have the initial twinge of pain from the median nerve inside your wrist getting squeezed. First you get the fast pain, which is followed a bit later by the dull pain. Fast pain is a signal from a pain receptor that travels along an A nerve fiber. Dull pain is a pain signal that travels on a C nerve fiber.

The difference in the speed of sharp pain and dull pain comes from the different nerve fiber types. The A fibers are myelinated - they're wrapped in an insulating sheath that helps nerve signals travel faster. The C fibers are smaller and don't have the myelin wrapper, so it takes a few seconds for the signal to reach the brain.

As the nerve signal leaves the pain site at the wrist, it travels up the median nerve to the brachial plexus in the shoulder, where it splits into the medial cord and the lateral cord. The cords then further split and merge into the five root nerves connected to the spinal segments.

The pain signal enters the spinal cord at the dorsal horn, which can change the intensity of the signal. If you're pre-occupied with something, the dorsal horn can block the pain from reaching your brain. Then when you stop doing whatever you were doing, you start feeling the pain.

From the spinal cord, the pain signal travels via the spinothalamic tract to the brain. And now you're in pain.

Sensors

Okay. Now we know the road pain travels. But what is it exactly?

Our sensory neurons detect changes in their neighborhood. There are sensors all around your body, for example on the skin and eyes, in your muscles, joints, organs and the digestive tract. These sensors are not only for pain, but are also responsible for sensory perception and your body sense (i.e. the position of your limbs relative to each other).

Different sensor neurons detect pressure changes, stretching, presence of chemicals, and temperature changes. The pain sensors are tuned to fire only when the stimuli exceeds a specific threshold. The threshold isn't fixed, and can change as a result to changes in the environment. For example, a gentle touch can be quite painful on an inflamed area.

As the sensor is stimulated, it builds up an electric potential. As it exceeds the threshold value, it sets off an action potential (a kind of wave of flipped polarity) down the nerve. Electric? Yeah, all your cells maintain -70mV voltage between the inside and outside of the cell. Messing with this voltage is what neurons use for internal messaging.

A neuron consists of a receiving end and transmitting end. The two ends of a neuron are connected by a cable called the axon. The receiving end sets off the action potential to tell the transmitting end to release neurotransmitter molecules. These are picked up by the receiving ends of the neurons next in the chain (which makes them more or less likely fire off their own action potentials). There are hundreds of different neurotransmitters, but each neuron usually releases only one kind. Pain sensors use glutamate? Noradrenaline?

Putting it all together, tissue damage causes immune cells to release cytokines and prostaglandins that create inflammation which releases histamines and other molecules that are picked up by nociceptors, making them more sensitive and turning the inflamed area painful to touch. The inflammation also leads to the production of lysophosphatidic acid and sphingosine-1-phosphate that directly activate TRPV1 high temperature nociceptors responsible for burning sensations, causing a voltage potential buildup that exceeds the nociceptor's threshold, making it fire an action potential to its A fiber and C fiber axon ends, where the change in voltage triggers the intake of calcium ions into the cell, which signals the axon to bring neurotransmitter vesicles to pores in the cell membrane and release the contained glutamate molecules into the synaptic cleft, where the dendrite of the next neuron picks them up and excites the neuron, making it propagate the signal. On reaching the spinal column, the dorsal horn attenuates the pain signal with GABA and noradrenaline neurotransmitters before forwarding it on along the spinothalamic tract to the brainstem and thalamus. And now you're feeling burning pain at the inflammation site and it's become sensitive to touch.

This feels like one of those "what happens when you click on a link"-explainers that ends up with an explanation of how to build an adder circuit out of transistors. Anyway, that was an educational journey.

Nociceptor Sensory Neuron-Immune Interactions in Pain and Inflammation https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5205568/

General Pathways of Pain Sensation and the Major Neurotransmitters Involved in Pain Regulation https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6121522/

Presynaptic Inhibition of Pain and Touch in the Spinal Cord: From Receptors to Circuits [PDF] https://www.mdpi.com/1422-0067/22/1/414/pdf

BatWerk 2 - On muscles

This is a series of blog posts that talks about the different aspects of an exercise app and how we're approaching them in BatWerk (Intro, How do muscles work, Pains, Maintaining the routine, How to play). Interested? How would you like to improve it?

The goal of the BatWerk exercise app (Android / iOS) is to keep you healthy, happy and productive without requiring you to overhaul your entire life.

So, of course I ended up wandering down some researchy rabbit holes to figure out how to do that. One of these was figuring out what actually happens when you do exercise. Why does your body move in the first place and how does it go about achieving that. Here are some confused notes on the whole process. Comments and corrections welcome, I'm out of my depth here!

What's a Muscle Anyway

Hey, your muscles are bags of string-like proteins that slide across each other with the help of ATP molecules. The proteins start moving and using ATP after calcium ions released by motor nerve activation open a lock molecule. Each of the sliding proteins generates force on the piconewton scale. To lift your arm, trillions of proteins need to slide in unison.

The three ways to make your muscles work better are to increase the number of muscle proteins, increase the amount of ATP available, and improve the motor nerve firing.

Moving a muscle activates it and makes it grab oxygen, sugars and fat from your bloodstream for ATP generation. The more capillaries you've got around the muscle, the more ATP it has available. Activating muscles also drives growth hormone secretion, which makes the muscles grab proteins from the bloodstream for conversion into muscle protein, and stimulates the growth of capillaries. Conversely, inactive muscles go into power saving mode where they don't pull in fuel and proteins, leading to lower metabolic rate and loss of muscle proteins.

Activating muscles to perform motions also trains your motor nerves to fire at the right time. Motor nerves activate only a part of the available muscle fibriles to contract, cycling through these activation groups over the contraction period. Motor nerves need to be trained through repeated use. Moves also require technique training to accomplish them through muscle contractions.

The ATP used by the proteins comes in four ways. First is the existing reserves inside the muscle. These are used up in about 3 seconds. Then come the muscle's creatine phosphate reserves. These are converted to ATP and last for a bit more than 5 seconds. Next up is anaerobic conversion of sugars to ATP, which can be maintained for a minute or two. After that, the muscle switches to aerobic ATP conversion from sugars if available, falling back to fats and even proteins if not.

Anaerobics

The thing about anaerobic and aerobic conversion is that aerobic conversion of sugars is around 15 times more efficient than anaerobic (30 aerobic ATP per glucose molecule vs 2 anaerobic ATP per glucose molecule). If you operate aerobically, you'll have to do 15 times the work to process the same amount of sugar. In other words, a 800m sprint needs to process as much sugar as a 10k run.

Sounds wasteful, right? But your body has a trick up its sleeve, called the Cori cycle. The anaerobic splitting of glucose also yields two molecules of pyruvate that get fermented to lactate. In the Cori cycle, the lactate is taken to the liver and converted back to glucose. However, this conversion uses up  6 ATP molecules, so it's not a perpetual motion sugar-recycling machine. In aerobic ATP generation, the pyruvate is taken through the Krebs cycle in mitochondria instead.

So, while on the whole, the Cori cycle loses 4 ATP, the liver's ATP molecules can come from aerobic generation of ATP before or after the anaerobic exercise. If you go through the Cori cycle once before switching to aerobic generation of ATP, you'll generate 26 ATP with the Cori cycle vs 30 ATP when fully aerobic. Less efficient, sure, but not 2 vs 30.

This creation of glucose from other molecules is called gluconeogenesis and it's also how your body maintains your blood sugar levels during intense exercise, starvation or a low-carb diet. In a way, your body is a factory dedicated to converting stuff to glucose, storing it, transporting it, and creating ATP out of it. Which makes sense on a cellular level, cells are all about breaking down complex molecules for energy and using the energy to build other complex molecules.

ATP ADP GTP GDP NAD NADH FAD FADH2 WHAT

ATP molecules aren't so much created from sugar, as they are "recharged". When a muscle protein uses ATP to do its tiny sliding walk, the ATP is converted into ADP by breaking off one phosphate group. This ADP then gets turned back into ATP by attaching the phosphate group back to it.

ADP stands for adenosine diphosphate, and ATP stands for adenosine triphosphate, so you can see how the addition of a phosphate turns a diphosphate into a triphosphate and vice versa. And yes, there's also AMP, or adenosine monophosphate.

Similarly, the NAD+ and FAD+ ions (nicotinamide adenine dinucleotide and flavin adenine dinucleotide, respectively. Those adenines keep popping up everywhere, huh?) are recharged to NADH and FADH2 molecules in the Krebs cycle.

The Krebs cycle can generate either ATP or GTP (guanosine triphosphate). GTP can be converted to ATP by swapping the phosphate chain of an ADP for the GTP's one. This is done by a molecular machine called the nucleoside-diphosphate kinase that turns the ADP into an ATP and the GTP into a GDP (guanosine diphosphate). This swap can be done in the other direction as well. Muscle cells tend to generate ATP in the Krebs cycle as they use a lot of ATP. Other tissues like the liver can generate more GTP, as it's useful in protein synthesis.[Citric Acid Cycle]

Right. To wrap up, your muscle cells break down sugar to convert ADP to ATP by adding one phosphate group to it. The ATP is used by the proteins in your muscles to help them climb past each other, which breaks off the phosphate group and creates ADP. The sugar can be processed anaerobically or aerobically. The aerobic processing is an extra phase added after the anaerobic process, and can be delayed for a later date with the help of lactic acid.

This sugar processing cycle is happening right now inside each of the 37 trillion cells of your body. Every move you make requires coordinating trillions of proteins to react in the right way at the right time.

BatWerk - Intro

The goal of the BatWerk exercise app (Android / iOS) is to keep you healthy, happy and productive without requiring you to overhaul your life. This is a series of blog posts that talks about the different aspects of an exercise app and how we're approaching them in BatWerk (Intro, How do muscles work, Pains, Maintaining the routine, How to play). Interested? How would you like to improve it?

The Purpose

I believe that people can live healthier, happier and more meaningful lives with technological assistance. To wit, I believe _I_ can live a healthier, happier and more meaningful life with tech to help me. There's still some time left to live, and I'd rather live them feeling good instead of collapsing into a shambling creaky tangle of pain.

So I made a small free exercise app called BatWerk (Android / iOS) to keep myself from hurting at the end of the day. It's been working pretty well, back pains are mostly gone and neck pain is less frequent (and I have a script to deal with it). Better mood and sleep too. It's awesome (well, I would say that, wouldn't I?)

How does it work?

BatWerk challenges you to complete 12 rings over the day. Each ring takes about 2 minutes of easy moves to complete. Easy as in "Lift your arms to your sides ten times"-level of challenge. The moves are randomly picked from a selection of 40 exercises.

The trick with the rings is that the next ring unlocks on the next half hour. To complete all 12, you'll need to move a bit every now and then over six hours.

So it's a bit different from your run-of-the-mill exercise app. You use it constantly. It uses messaging to boost your mood. It doesn't really try make you sweat. Its goal is to periodically wake up your main muscle groups and maintain your mobility.

Obligatory screenshot from a version from 6 months ago.

How did this come about?

At first, the app was about doing this 15-minute workout. Just reminding you of the moves and the reps. Then taking you through a quest to the workout dungeon. Warmup on the afternoon fields, first set at the dungeon entrance, second set in the hall of warriors, third set in the volcanic mines, and the fourth set in the evil hall of lava with blood-red fog swirling about. After finishing the workout, you'd fly to the blue skies to do stretches.

It was good. But too much and too little at the same time. The workout needs a reasonably cool place, workout clothes, and half an hour of buffer for shower and changing clothes. It'll also beat you up pretty good, so you can't really do it several times a day (well, unless you're developing the app and need to test it.) Too hard and time-consuming, and it doesn't keep you moving throughout the day.

Back to the drawing board. Let's try an infinite sequence of random moves. Just open the app and move. Okay, this is easy and quick to do. I could do some of this every day. But, how often should you move? What's a good pattern?

According to Exercised, you should move a bit every half hour. And to flush the fast energy reserves in your muscles, you only need 15 seconds of anaerobic exercise. Right. Let's plug these together into a game where you need to move every half hour, doing about four different moves, 15-30 seconds each. Forces a refresh cycle for the muscles involved and doesn't take much time.

Still, well, you can't move _every_ half an hour. What about the meetings? What about lunch? Not to mention that 2 minutes of exercise every waking 30 minutes is pretty exhausting.

The current design is a game where you try to collect 12 rings over the day. This way you don't have to move every half hour, but it still drives you to have 6 active hours a day.

The 12-ring game was working OK for about 8 months, but now I've had some slowdown, hitting only 3-6 rings for a few weeks. Could be just the summer heat making exercise a bad idea in general, but I see it as something that could be fixed in the design of the activity. If the goal of the app is to keep you active every day, it really should keep you active every day, not just on days where you feel like it.

Still, 3 rings is way better than zero rings. Six minutes of exercise spread across the day. Without the app, I'd be at zero minutes. Still, it creates feelings of inadequacy, even with the non-blaming nature of the app. I did eventually break out of the funk and get a few days of full rings in a row. But I'd like it to rescue you a bit more. Get you back on track faster.

Compute shader daemon

Riffing on the WebCompute experiment (run GLSL compute shaders across CPUs, GPUs and the network), I'm now thinking of making the GLSL IO runtime capable of hanging around and running shaders on demand. In WebCompute, the Vulkan runner ran a single shader and read work units from the STDIN (the network server was feeding the STDIN from a WebSocket).

With GLSL IO, that goal is extended to handle arbitrary new shaders coming at various times. On a high level, you'd send it a shader file, argv and fds for stdin/stderr/stdout through a socket. Then it would create a new compute pipeline, allocate and bind buffers and run the pipeline on a free compute queue. On completing a dispatch, it'd delete the pipeline and free the buffers. This cycle of recreation might be expensive, so it should have a cache for buffers and compute pipelines.

The compute shaders could share a global IO processor, or each could have its own IO processor thread. A global IO processor could be tuned to the IO CPU and have better coordination of the IO operations, but could end up with slow IO requests from one shader clogging the pipe (well, hogging the threadpool) for others. This could be worked around with async IO in the IO processor.

The other issue is the cooperative multitasking model of compute shaders. If your shader is stuck in an infinite loop on all compute units, other shaders can't run. To remedy this, the GPU driver allows compute shaders to run only a few seconds before it terminates them. On mobiles this can be as low as 2 seconds, on the desktop 15 seconds. If a discrete GPU has no display connected to it, it may allow compute shaders to run as long as they want.

If your shaders needs to run longer than 10 seconds, this is a problem. The usual way around it is to build programs that run a few milliseconds at a time, and are designed to be run several times in succession. With the IO runtime, this sounds painful. An IO request might take longer than 10 seconds to complete. Writing a program that issues a bunch of async IOs, terminates, polls on the IOs on successive runs and does less than 10 seconds of processing on the results (doing the restart loop if it's running out of runtime), then finally tells the runtime that it doesn't need to be run again. In the absence of anything better, this is how the first version of long-running shaders will work.

The second version would be a more automated version of that. A yield keyword that gets turned into a call to saveRegisters() followed by program exit. On program start, it'd do loadRegisters() and jump into the stored instruction pointer to continue execution. The third version would insert periodic checks for how long the program has been running, and yield if the program's been running longer than the scheduler slice time.

Of course, this is only useful on GPU shaders. If you run the shaders on the CPU, the kernel's got you covered. The IO runtime is still useful since high-performance IO doesn't just happen.

I think the key learning from writing the GLSL IO runtime has been that IO bandwidth is the only thing that matters for workloads like grep. You can grep on the CPU at 50 GB/s. You can grep on the GPU at 200 GB/s. But if you need to transfer data from the CPU to the GPU, the GPU grep is limited to 11 GB/s. If you do a compress-decompress pipe from CPU to GPU, you can grep at 24 GB/s (if the compression ratio is good enough). GPUs give you density, but they don't have enough bandwidth to DRAM to really make use of the compute in common tasks.

Getting to even 11 GB/s requires doing multithreaded IO since memcpy is limited to 7 GB/s per thread. You need to fetch multiple blocks of data in parallel to get to 30 GB/s. Without the memcpy (just reading), you should be able to reach double the speed.

GPU IO library design thoughts

Thinking about the design of file.glsl, a file IO library for GLSL.

For a taste, how about calling node.js from a GPU shader:

string r, fn = concat("node-", str(ThreadID), ".txt");
awaitIO(runCmd(concat(
  "node -e 'fs=require(`fs`); fs.writeFileSync(`", 
  fn,
  `, http://Date.now().toString())'"    
)));
r = readSync(fn, malloc(16));
println(concat("Node says ", r));

There are more examples in the test_file.glsl unit tests.

Design of GPU IO

Hardware considerations

• GPUs have around a hundred processors, each with a 32-wide SIMD unit.
• The SIMD unit can execute a 32 thread threadgroup and juggle between ten threadgroups for latency hiding.
• GPU cacheline is 128 bytes.
• CPU cacheline is 64 bytes.
• GPU memory bandwidth is 400 - 1000 GB/s.
• CPU memory bandwidth is around 50 GB/s.
• PCIe bandwidth 11-13 GB/s. On PCIe4, 20 GB/s.
• NVMe flash can do 2.5-10 GB/s on 4-16 channels. PCIe4 could boost to 5-20 GB/s.
• The CPU can do 30 GB/s memcpy with multiple threads, so it’s possible to keep PCIe4 saturated even with x16 -> x16.
• GPUdirect access to other PCIe devices is only available on server GPUs. Other GPUs need a roundtrip via CPU.
• CPU memory accesses require several threads of execution to hit full memory bandwidth (single thread can do ~15 GB/s)
• DRAM is good at random access at >cacheline chunks with ~3-4x the bandwidth of PCIe3 x16, ~2x PCIe4 x16.
• Flash SSDs are good at random access at >128kB chunks, perform best with sequential accesses, can deal with high amounts of parallel requests. Writes are converted to log format.
• Optane is good at random access at small sizes >4kB and low parallelism. The performance of random and sequential accesses is similar.

• => Large reads to flash should be executed in sequence (could be done by prefetching the entire file to page cache and only serving requests once the prefetcher has passed them)
• => Small scattered reads should be dispatched in parallel (if IO rate < prefetch speed, just prefetch the whole file)
• => Writes can be dispatched in parallel with more freedom, especially without fsync. Sequential and/or large block size writes will perform better on flash.
• => Doing 128 small IO requests in parallel may perform better than 16 parallel requests.
• => IOs to page cache should be done in parallel and ASAP.
• => Caching data into GPU RAM is important for performance.
• => Programs that execute faster than the PCIe bus should be run on the CPU if the GPU doesn’t have the data in cache.
• => Fujitsu A64FX-type designs with lots of CPU cores with wide vector units and high bandwidth memory are awesome. No data juggling, no execution environment weirdness.

Software

The IO queue works by using spinlocks on both the CPU and GPU sides.
The fewer IO requests you make, the less time you spend spinning.
Sending data between CPU and GPU works best in large chunks.

To avoid issues with cacheline clashes, align messages on GPU cacheline size.
IO request spinlocks that read across the PCIe bus should have small delays between checks to avoid hogging the PCIe bus.
Workgroups (especially subgroups) should bundle their IOs into a single scatter/gather.

When working with opened files, reads and writes should be done with pread/pwrite. Sharing a FILE* across threads isn’t a great idea.
The cost of opening and closing files with every IO is eclipsed by transfer speeds with large (1 MB) block sizes.

The IO library should be designed for big instructions with minimal roundtrips.
E.g. directory listings should send the entire file list with file stats, and there should be a recursive version to transfer entire hierarchies.
Think more shell utilities than syscalls. Use CPU as IO processor that can do local data processing without involving the GPU.

Workgroup concurrency can be used to run the same code on CPU and GPU in parallel. This extends to multi-GPU and multi-node quite naturally.
The IO queue could be used to exchange data between running workgroups.

Limited amount of memory that can be shared between CPU and GPU (I start seeing issues with > 64 MB allocations).
Having a small IO heap for each thread or even threadgroup, while easy to parallelize, limits IO sizes severely.
32 MB transfer buffer, 32k threads -> 1k max IO per thread, or 32k per 32-wide subgroup.
Preferable to do 1+ MB IOs.
Design with a concurrently running IO manager program that processes IO transfers?
The CPU could also manage this by issuing copyBuffer calls to move data.

Workgroups submit tasks in sync -> readv / writev approach is beneficial for sequential reads/writes.
Readv/writev are internally single-threaded, so probably limited by memcpy to 6-8 GB/s.

Ordering of writes across workgroups requires a way to sequence IOs (either reduce to order on the GPU or reassemble correct order on the CPU.)
IOs could have sequence ids.

Compression of data on the PCIe bus could help. 32 * zstd --format=lz4 --fast -T1 file -o /dev/null goes at 38 GB/s.

[Update] Did a quick test with libzstd (create compressor context for each 1 MB read, compress, send data to GPU) with mixed results. Getting 3.4 GB/s throughput with Zstd. Which is good for zero-effort, but I should really be using liblz4. Running 32 instances of zstd --fast in parallel got 6.4 GB/s, with --format=lz4 16 GB/s.

[Update 2] Libzstd with fast strategy and compression level -9 can do 12.7 GB/s grep.glsl throughput. So if I had a GPU-side decompressor, I might see a performance benefit vs raw data (11.4 GB/s). On already-compressed files, there's a 10-15% perf penalty vs raw.

[Update 3] LZ4 with streaming block compressor and compression level 9 reaches 17.5 GB/s grep.glsl throughput on the above file, 22.5 GB/s on a 13 GB kern.log file (lots of similar errors). About 5% perf penalty on compressed files. Feels like a GPU decompressor could actually be a good idea.

Caching file data on the GPU is important for performance, 40x higher bandwidth than CPU page cache over PCIe.
Without GPU-side caching, you’ll likely get better perf on the CPU on bandwidth-limited tasks (>50 GB/s throughput.)
In those tasks, using memory bandwidth to send data to GPU wouldn’t help any, best you could achieve is zero slowdown.
(Memory bandwidth 50 GB/s. CPU processing speed 50 GB/s. Use 10 GB/s of bandwidth to send data to GPU =>
CPU has only 40 GB/s bandwidth left, GPU can do 10 GB/s => CPU+GPU processing speed 50 GB/s.)

Benchmark suite

• Different block sizes
• Different access patterns (sequential, random)
  • Scatter writes
  • Sequential writes
  • Gather reads
  • Sequential reads
  • Combined reads & writes
• Different levels of parallelism
  • 1 IO per thread group
  • each thread does its own IO
  • 1 IO on ThreadID 0
  • IOs across all invocation
• Compression
• From hot cache on CPU
• From cold cache
• With GPU-side cache
• Repeated access to same file
• Access to multiple files

Does it help to combine reads & writes into sequential blocks on CPU-side when possible, or is it faster to do IOs ASAP?

Caching file descriptors, helps or not?

grep.glsl

grep.glsl is sort of working. It's a GLSL compute shader version of grep. A very simple one at that. It tests a string against a file's contents and prints out the byte offsets where the string was found.

The awesome part of this is that the shader is running the IO. And it performs reasonably well after tuning. You could imagine a graphics shader dynamically loading geometry and textures when it needs them, then poll for load completion in following frames.

Here are the few first lines of grep.glsl

    string filename = aGet(argv, 2);
    string pattern = aGet(argv, 1);

    if (ThreadLocalID == 0) done = 0;

    if (ThreadID == 0) {
        FREE(
            println(concat("Searching for pattern ", pattern));
            println(concat("In file ", filename));
        )
        setReturnValue(1);
    }

Not your run-of-the-mill shader, eh?

This is the file reading part:

    while (done == 0) {
        FREE(FREE_IO(
            barrier(); memoryBarrier();

            // Read the file segment for the workgroup.
            if (ThreadLocalID == 0) {
                wgBuf = readSync(filename, wgOff, wgBufSize, string(wgHeapStart, wgHeapStart + wgBufSize));
                if (strLen(wgBuf) != wgBufSize) {
                    atomicAdd(done, strLen(wgBuf) == 0 ? 2 : 1);
                }
            }

            barrier(); memoryBarrier();

            if (done == 2) break; // Got an empty read.
            
            // Get this thread's slice of the workGroup buffer
            string buf = string(
                min(wgBuf.y, wgBuf.x + ThreadLocalID * blockSize),
                min(wgBuf.y, wgBuf.x + (ThreadLocalID+1) * blockSize + patternLength)
            );

            // Iterate through the buffer slice and add found byte offsets to the search results.
            int start = startp;
            i32heapPtr = startp;
            for (int i = 0; i < blockSize; i++) {
                int idx = buf.x + i;
                if (startsWith(string(idx, buf.y), pattern)) {
                    i32heap[i32heapPtr++] = int32_t(i);
                    found = true;
                }
            }
            int end = i32heapPtr;

            ...

Performance is complicated. Vulkan compute shaders have a huge 200 ms startup cost and a 160 ms cleanup cost. About 60 ms of that is creating the compute pipeline, the rest is instance and device creation.

Once you get the shader running, performance continues to be complicated. The main bottleneck is IO, as you might imagine. The file.glsl IO implementation uses a device-local host-visible volatile buffer to communicate between the CPU and GPU. The GPU tells the CPU that it has some IO work for the CPU by writing into the buffer, using atomics to prevent several GPU threads from writing into the same request. The CPU spinlocks to grab new requests to process, then spinlocks for the requests to become available. After processing the request, the CPU writes the results to the buffer. The GPU spinlocks awaiting for the IO completion, then copies the IO results to its device-local heap buffer.

The GPU-GPU copies execute reasonably fast (200+ GB/s), but waiting for the IO drops the throughput to around 6 GB/s. This is way better than the 1.6 GB/s it used to be, when it was using int8_t for IO and ~200 kB transfers. Now the transfer buffer is 1 MB and the IO copies are done with i64vec4.

Once you have the data on the GPU, performance continues to be complicated. Iterating through the data one byte at a time goes at roughly 30 GB/s. If the buffer is host-visible, the speed drops to 10 GB/s. Searching a device-local buffer 32 bytes at a time using an i64vec4 goes at 220 GB/s.

The CPU-GPU transfer buffer has a max size of 256 MB. The design of file.glsl causes issues here, since it slices the transfer buffer across shader instances, making it difficult to do full-buffer transfers (and minimize IO spinning). Now grep.glsl does transfers in per-workgroup slices, where 100 workgroups each do a 1 MB read from the searched file, then distribute the search work across 255 workers per workgroup.

This achieves 6 GB/s shader throughput. The PCIe bus is capable of 12 GB/s. If you remove the IO waits and just do buffer copies, the shader runs at 130 GB/s. Taking that into account, the shader PCIe transfers should be happening at 6.3 GB/s. Removing the buffer copies had a very minimal effect on throughput, so doing the search directly on the IO buffer shouldn't improve performance by much.

Thoughts

Why are the transfers not hitting the PCIe bus limits? Suspiciously hovering at around half of PCIe bandwidth too. Could it be that the device-local buffer is slow to write to from the CPU side? Previously I had host-cached memory for the buffer, which lets you do flushes and invalidations to (hopefully) transfer in more efficient chunks. The reason that I'm not using a host-cached memory buffer is that GLSL volatile doesn't work for host-side memory: the GPU seems to cache fetched memory into GPU RAM and volatile only bypasses the GPU L1/L2 caches, so you'll never see CPU writes that landed after your first read. And there doesn't seem to be a buffer type that's host-cached device-local.

Maybe have a CPU-side buffer for IO, and a transfer queue to submit copies to GPU memory. This should land the data into GPU RAM and volatile should work. Or do the fread to a separate buffer first, then memcpy it to the GPU buffer.

Vulkan's startup latency makes the current big binary approach bad for implementing short-lived shell commands. The anemic PCIe bandwidth makes compute-poor programs starve for data. GNU grep runs at 4 GB/s, but you can run 64 instances and achieve 50 GB/s [from page cache]. This isn't possible with grep.glsl. All you have is 12 GB/s.

Suppose this: you've got a long-running daemon. You send it SPIR-V or GLSL. It runs them on the GPU. It also maintains a GPU-side page cache for file I/O. Now your cold-cache data would still run at roughly the speed of storage (6 GB/s isn't _that_ bad.) But a cached file, a cached file would fly. 400 GB/s and more.

Creating the compute pipeline takes around 50 ms. Caching binary pipelines for programs would give you faster startup times.

The GPU driver terminates running programs after around 15 seconds. And they hang the graphics while running. Where's our pre-emptive multitasking.

This should really be running on a CPU because of the PCIe bottleneck and the Vulkan startup bottleneck. Going to try compiling it to ISPC or C++ and see how it goes.

[Update] Tested memcpy performance. Single thread CPU-CPU, about 8 GB/s. With 8 threads: 31 GB/s. Copying to the device-local host-visible buffer: 8 GB/s with one thread. With 4 threads, 10.2 GB/s. Cuda bandwidthTest can do 13.1 GB/s with pinned memory and 11.5 GB/s with pageable memory. The file.glsl IO transfer system doesn't seem to be all that slow, it just needs multi-threaded copies on the CPU side.

Built a simple threaded IO system that spawns a thread for every read IO up to a maximum of 16 threads in flight. Grep.glsl throughput: 10 GB/s. Hooray!

[Update 2] Lots of tweaking, debugging and banging-head-to-the-wall later, we're at 11.45 GB/s.

file.glsl

Current design: Each shader invocation has an 8k heap slice and an 8k IO heap slice. There's an IO request buffer. GPU writes IOs to the req buffer, CPU picks them up and writes the result to the IO heap. The GPU copies the result from the IO heap to the main heap. The IO heap and the IO request buffer are marked volatile. The main heap isn't, so it can benefit from caches.

Now trying to handle argv nicely. Allocate an extra slice in the heap and copy the argv there before shader start. 

This could also be used to store string literals. Now string literals are malloc'd and filled in each invocation at shader start, which is a total waste of time. But because the string lib has funcs that do in-place modification, this avoids one class of errors. Switching to immutable strings in the lib is an enticing option.

Memory allocation is done with a simple bump malloc. Freeing heap memory after use is a hassle. I have macros FREE() and FREE_IO() that free whatever heap / IO heap allocations you did inside the call. 

It might be nice to have a global heap with a proper malloc to store large allocations that are re-used across threads. E.g. for loading texture data. This would probably have to be a fixed size buffer. I doubt that it's possible to allocate more buffer memory on the CPU side while the shader is running. Would be nice though!

Wrote a sketch of grep.glsl. Very educational, as it exposed a bunch of missing features and "this'd be nice to have"-things. Handling argv and program return value fall in the first category. Having helpers for reductions across all invocations and sorted-order IO fall in the second category. 

The current grep.glsl sketch is: each thread does a read for a 4kB+strLen(pattern) chunk, then runs indexOf(chunk, pattern) to find all occurrences of pattern in it. The threads then iterate through all invocationIDs in order (with a barrier() call to keep them in lockstep) and when the thread id matches the current id, the thread prints out its results. This should keep the workgroup threads in order, but the workgroups might still be in different order. Then the threads or-reduce whether they found any hits or not to set the program return value to 0 or 1. Advance read offset by total thread count times 4kB, repeat until a thread reads less than 4kB (EOF).

This makes a bunch of design issues apparent. The IOs should be run concurrently. Copying IO bytes to heap has limited value here, so having a way to run string functions directly on the IO heap would be nice. The read could be done with a single IO instead of threadCount IOs. Overlapping IO and execution: could issue two IOs, wait for the first, issue third IO, process first IO, wait for the second, issue fourth IO, process second IO, ... How to do line numbers. Reads should have an EOF flag. Can we hit 12 GB/s for files in page cache? Can we cache files in GPU RAM and match more patterns later at 400 GB/s?