3 ms·
> If you eg still use a linked list data structure as an input, you are never gonna be faster than O(n) no matter how clever your implicit parallelism is. I th
by sedachv 9y ago
> If you eg still use a linked list data structure as an input, you are never gonna be faster than O(n) no matter how clever your implicit parallelism is.
I think you took away completely the wrong point from Steele's talk. The bottleneck is not in the data structures, it is in the control flow, which is just a trivial way of restating Amdahl's law. In fact Steele co-wrote an excellent expository paper with Daniel Hillis, while they were at Thinking Machines, showing how to do parallel processing on linked lists:
http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-data-parallel-algorithms.pdf http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-d...
- eru 9y agoI was in the audience and asked questions, and chatted with him afterwards.. Data flow dictates control flow (to a certain extent). The paper you linked to is very interesting: but even there they have to augment their 'linked list' with more links. And they assume one processor per list element and don't count the set-up time of having each processor find its list element. (There's some more complication to it. But I am glad between 1986 when the paper was written and 2009 when he gave the talk, he figured out how to explain some of these issues more simply.)