Could you not do something like chunk the input and operate on the pieces in parallel? I'd think you could use something like a rope (à la text editors) to support the concurrent writes.

(I may or may not have forgotten the differences between concurrency and parallelism.)