Running ASCEND, DESCEND and PIPELINE algorithms in parallel using small processors (Q1210315)

We propose a scheme for generating addresses using ``small'' processors. We use this scheme to show that a large class of parallel algorithms (of size \(n\)) can be run (without overheads in time) using \(n\) processors (each of wordsize \(\Omega(\log\log\log n)\) bits) and \(\text{poly}(n)\) memory, where \(\text{poly}(n)\) is \(O(n^ c)\), for constant \(c\). Though the word size of the processors still increases with the number of processors used, it does so extremely slowly.