The main issue you focus on are: 1. pipelined instruction broadcast 2. reduction operations 3. pipelined processing elements 4. data caches Instruction Broadcast On the instruction broadcast side, we do in fact use pipelining to hide the latency; no rocket science there. But we didn't need to derive much of a hierarchical network: two stages of distribution pipelining is enough if we use reasonably tight physical construction, with wire lengths shorter than two feet (4ns). The hard part is dealing with transmission line effects and the sheer number of instruction wires. You can easily get sub-nanosecond 1:8 fanout chips in ECL (the bug is that they're SSI), so that you can fan out very very quickly. The problem is that each additional capacitive load on the parallel-terminated instruction bus 1) causes a slight impedance mismatch and 2) lowers the impedance of the wire. Those effects limit the effective fanout. But unlike your model, there really doesn't have to be a register at every fanout stage. Registers become necessary because of time-of-flight along the wire, and not because of cycle time or fanout. Given a relatively old process (say the 0.5 micron HP14G available through MOSIS), I can make each Abacus PE run near 180 MHz (unpipelined, but that's another story). Cycle time becomes 5.5 ns. If 2:1 instruction multiplexing is used to reduce the pin count, we have to send a bit in 2.75 ns, which is about a foot and a half of wire. So your tree-based model still works, but your constants need to be derived from different physical reasons. Also, there's no good reason for different stages to have identical fanout factors, since there are differences both between inter-board and on-board wire delays, and between the receiving circuitry. It so happens that our design does have three stages of 4:1 fanout, but that's a coincidence, and only two stages are actually registered. In our 16-board, 256-chip (256K PEs) design, the instructions are read out of memory, multiplexed (since we don't have 4ns SRAMs), converted to ECL and registered. This is stage one. Each instruction bit is fanned out to four buffers; each buffer drives a wire to four boards through parallel-terminated bus. This is slightly conservative; we think that with differential signalling we could get 8:1 to work. The signals are registered on each board and then fanned out by another factor of 4:1 to four column bus drivers. Each column consists of just under 2 feet of PCB trace with four chips on it. As you can see, the factor of 4 is coincidental. Changing the topic a bit, Rockoff's whole thesis is a complicated solution to a non-problem. His argument for requiring instruction caches is based on fundamental limitations on instruction skew and driver chip uncertainties. For example, lot-to-lot variation between ECL drivers mean that two adjacent instruction bits can arrive up to 1.5 ns apart, crossing a clock boundary. Our solution is to have on-chip pipeline stages to re-time the instructions on a bit-by-bit basis. Each input pad is backed by a 4-bit deep buffer. Through programmable feedback, each bit determines which stage to tap for its instruction. Thus, chips far away (2 feet = 4ns) from the driver receive their signals late and use the very first pipeline register, while nearer chips use the second or third stage, equalizing the delay. So the expense of replicating instruction caches on each chip is eliminated for the price of 4 registers and a bit of control logic for each bit. Reduction Hazards This is an important point, and one that you've thought of in more detail than we have. We just assumed that the global OR computation already required about 5 or 6 cycles, the extra two cycle cost of pipelining was negligible, especially when the controller runs at least two (and possibly four) times slower than the parallel array. For any reasonable implementation, the pipeline cost is either zero or one one extra stall cycle per compare. Any code we looked at had an inner loop of at least 10 cycles, so the extra pipelining cost was at most 5%. In the pathological case of a very tight loop, there is a software technique for reducing the effect of a pipeline stall. Most iterative code does not damage the solution if it executes an extra iteration or two. Our solution is to unroll the loop, checking for completion only once every 3 or 4 iterations. Since iterative code usually executes for at least dozens of iterations, the extra two or three iterations at the end are reduced to a 10\% cost. In summary, we didn't think that reduction hazards were very important. Of course, we didn't use the same code sets as you did. I'd be interested to find out whether the technique applies to the benchmarks you used. Also, your analysis [and ours] indicates that pipelining *always* helps, just not as much as one would hope. Pipelined PEs This is a critical point. The last chapter of my thesis proposes a complete redesign of the Abacus PE based exactly on the unsuitability of the architecture for pipelining. In the general case, pipelining SIMD PEs is a no-brainer. The advantages are identical to pipelining conventional RISCs, with the extra benefit (as you pointed out) of nonexistent branch delay penalties. So of course PEs should be pipelined, right? A slight unanticipated penalty occurs in the case of simple one-bit PEs for two reasons. First, the forwarding/bypass logic is bigger than the ALU itself. The overall area increase is on the order of 10-20%. This is an acceptable penalty, in light of the fourfold performance improvement. On the other hand, the Abacus PE can already run at 125 MHz unpipelined in a 1 micron technology. A pipelined implementation in a 0.5 micron process would hit 800 MHz. Instruction delivery, as well as on-chip signal distribution would become very very challending. Power dissipation is currently about 20 W at 125 Mhz, and is currently the main limination on circuit board packing density. A higher clock rate would complicate the design substantially. But the main drawback of the Abacus design is the reconfigurable nature of the processors. The PEs use the network during almost every arithmetic operation. As a result, they effectively require a synchronization step at almost every cycle, which inserts a stall into the pipeline. As a result, pipelining becomes almost useless. Memory We completely agree on this point. My analysis shows that off-chip memory latency is the key determinant of performance. Especially when users insist on running programs with more sites than physical processors. High virtual processor ratios guarantee frequent off-chip memory accesses. The Abacus-1 chip uses a 64-bit bus to off-chip memory running at 16ns, and the bandwidth-limited latency is still on the order of 40 cycles, an order of magnitude more time than a typical arithmetic operation. As far as SIMD clock cycles "at or near DRAM times", that time is long past. Abacus runs an order of magnitude faster than DRAM latencies. The only reason we can afford that much fast memory near the processors is because we use Ramtron's RDRAM, which integrates a small SRAM cache in a DRAM chip. I'm interested in how you obtained table 3. Surely fMEM depends on the virtualization ratio? Or did you assume a 1:1? My next favorite topic is data caches for SIMD computers. Obviously, if each PE is allowed indepedent memory addressing, data caches are useless, since the entire array must wait if *any* PE misses its cache, which will occur with a probability near unity. On the other hand, if every PE uses the same memory address, data caches are great, since all PEs will either hit or miss, ad so the control/tag logic can be amortized over a large number of memory cells. We've found that many of the algorithms we're interested in are "oblivious" in the sense that the address traces are known at compile time. We therefore decided to use explicitly managed SRAM. The other advantage of this approach is that we didn't have to do yet another custom VLSI part. Like the MP-2, Abacus supports background loading: while a memory access is executing, the machine can perform other instructions. All the memory transfer hardware is under compiler control, so off-chip memory can be upgraded, if necessary. We were very happy with this feature because it was very cheap to implement. Unfortunately, it only helps substantially (ie, factors of 2) in some relatively narrow regimes of miss probability $p$ and latency L. I'll make the postscript plot available, if you're interested). So here's an example of a feature we put in without careful preliminary simulation. The DOD cache idea is interesting for non-oblivious algorithms. Fortunately for the argument in favor of explicitly managed caches, three of the four benchmarks you use are oblivious! Neural networks with fixed connections certainly result in fixed traces. Median filters can be unrolled, and almost any matrix operations (probably including Cholesky) are oblivious. The only holdout is the M/M/1 benchmark. I wonder if the right answer in general is a single piece of hardware can function at different times as a conventional memory and as a cache. Area Cost Although I'm not sure why you included the so-called 'first model'. I don't know of any user of parallel code who would not rush to recompile his/her code if more PEs were added to the machine. The analysis in my thesis uses the equal area model. Practical limitations of the model are: Processor/cache area is a fraction of the chip size. Each PE requires additional communication pins, instruction drivers, and power/ground pins. SIMD chips are likely to be pad-limited, so there's only so many PEs that can be crammed on a chip effectively. Of course, multiple chips can be used, but key advantage of VLSI technology is high integration. More chips mean bigger, slower, and more fault-prone computers. DRAM processes tend to be a generation ahead of logic processes. So DRAM cores are substantially denser than logic cores. There's an IBM design (the Execube) which incorporates 16 32Kx9 DRAM cores with 16-bit SIMD PEs. Of course, most of us don't have access to this sort of technology and must use off-chip DRAM, which brings in pin-requirement issues. And in any case, you concluded that caches almost always help (unless they're too big). I heartily agree. A key feature of the Abacus architecture is its ability to reconfigure to provide exactly the right number of on-chip registers based on the problem.