Algorithms in the Ultra-Wide Word Model

Abstract. The effective use of parallel computing resources to speed up algorithms in current multi-core parallel architectures remains a difficult challenge, with ease of programming playing a key role in the eventual success of various parallel architectures. In this paper we consider an al-ternative view of parallelism in the form of an ultra-wide word processor. We introduce the Ultra-Wide Word architecture and model, an exten-sion of the word-ram model that allows for constant time operations on thousands of bits in parallel. Word parallelism as exploited by the word-ram model does not suffer from the more difficult aspects of paral-lel programming, namely synchronization and concurrency. For the stan-dard word-ram algorithms, the speedups obtained are moderate, as they are limited by the word size. We argue that a large class of word-ram al-gorithms can be implemented in the Ultra-Wide Word model, obtaining speedups comparable to multi-threaded computations while keeping the simplicity of programming of the sequential ram model. We show that this is the case by describing implementations of Ultra-Wide Word algo-rithms for dynamic programming and string searching. In addition, we show that the Ultra-Wide Word model can be used to implement a non-standard memory architecture, which enables the sidestepping of lower bounds of important data structure problems such as priority queues and dynamic prefix sums. While similar ideas about operating on large words have been mentioned before in the context of multimedia proces-sors [37], it is only recently that an architecture like the one we propose has become feasible and that details can be worked out.