This is getting deep in an ageing thread - do you want to take this to email? (It's in my profile)
Pipelined bzip2 wasn't in the evaluation for my research, but I bet remote stores would get considerably better results than software queues. Parallelising one algorithm is something of a stunt, and gets you just a single data point. Instead, I did a bunch of different benchmarks (microbenchmarks for FIFO queues and synchronisation barriers; larger benchmarks including a parallel profiler and a variable-granularity MapReduce to measure how far remote stores could move the break-even point for communication vs computation; and an oddball parallel STM system that I'd previously demonstrated on dedicated (FPGA) hardware). I got around an order of magnitude on all of them (some a little less, some much more).
The writeup starts on page 59 of https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-831.pdf and the evaluation on page 65.
Looking back, I seriously regret not taking more time to sit down and write it up more clearly, because I do think this should be interesting to serious CPU vendors. However, by that point I had reached the point of "I'm fed up with this PhD; I'm going home now". As I knew I didn't want to stay in academia, I published in a mediocre venue rather than revising for a better one, and went off to Silicon Valley instead. Your comments have made me re-read my old work, and it's painful to wonder how much further it could have gone if I had explained it better.