Fetch&Add and Queues

by Jack Richins

I spent most of today working on trying to implement a queue using "Fetch&Add" for use by a parallel quicksort alogrithm for a homework assignment, but I’m not pleased with the results.

Fetch&Add was introduced by the Ultracomputer project at NYU. The basic idea is in one operation you fetch the value in a memory location to a register and increment it’s value in memory. For example if in memory you had a value of 1 and 0x10, Fetch&Add(0x10, 1) would store 1 in the register and add 1 to the value of 1 in memory and at the end of the instruction 0x10 would contain 2.

This is really useful in parallel computing because it can reduce collisions. 2 processors can be trying to increment the same memory location and both can succeed. For example, it could be used as the index to an array where you want multiple processors to process the contents of the array. One by one the processors can efficiently see the value of the index it and increment so each processor is looking at a unique element of the array. I.e., processor 1 sees 0 and increments it to 1 using Fetch&Add. Processor 2 sees 1 and increments it to 2, and so forth. Very little blocking. In fact, according to my professor, the Ultracomputer had hardware that allowed multiple Fetch&Add instructions to be executed in the same instruction cycle, i.e. at the same time (not really at the exact same time, but since the increments happened very close to the memory rather than in the CPU, from the processors perspective it was happening at the same time).

Anyway, my problem is I came up with 2 solutions – one uses Fetch&Add to maintain 2 indexes, one to enqueue new sorting tasks and a second to dequeue them. But since I’m going over an array, I never really remove the tasks, just increment the pointer to where the next task should be read. My second solution was to use a single index for enqueuing and dequeuing. But then it’s really a stack, not a queue. Hmmm.

Anyway, that was my day :). That and eating out at Koho Cafe in Redmond. Loved the "cowboy" rib-eye steak in jalapeno butter. Definitely not healthy, but I enjoyed it.