Back to search

University of Waterloo

Performance of the Ultra-Wide Word Model

Abstract

dc:description.abstract

The Ultra-wide word model of computation (UWRAM) is an extension of the Word-RAM model which has an ALU that can operate on w^2 bits at a time, where w is the size in bits of a cell in memory. The purpose of this thesis is to explore the applicability of the UWRAM model, particularly when compared to the PRAM model, from an algorithmic point of view, to determine its potential for common applications. The work is divided into three sections: First we describe the model, its instruction set, strengths and weaknesses, and provide a few small examples that showcase the functionality of the model and how simple techniques can be used to speed up sequential algorithms. In the second section, we discuss the problem of sorting and searching, and show that elaborate data structures such as the fusion tree can be easily adapted to the model, allowing the sorting of n integers in O(n (log n/log log n) time with small constant factors. Lastly, we provide simulations of UWRAM and PRAM programs to solve two problems: subset sum and string matching. In the first case we show how a dynamic programming algorithm can be sped up using bit parallelism where traditional parallelism is difficult to achieve, and in the second, we show that even in a problem that is simple to parallelize traditionally, the UWRAM can perform well when compared to a PRAM.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pérez Gavilán Torres, Camila María
Advisors dc:contributor.advisor
  • Lopez Ortiz, Alejandro
  • Munro, J. Ian

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/12349

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pérez Gavilán Torres, Camila María. Performance of the Ultra-Wide Word Model. University of Waterloo, 2017. http://hdl.handle.net/10012/12349