Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Master of Science

Program

Computer Science

Collaborative Specialization

Scientific Computing

Supervisor

Dr. Marc Moreno Maza

Abstract

Parsing large expressions, in particular large polynomial expressions, is an important task for computer algebra systems. Despite of the apparent simplicity of the problem, its efficient software implementation brings various challenges. Among them is the fact that this is a memory bound application for which a multi-threaded implementation is necessarily limited by the characteristics of the memory organization of supporting hardware.

In this thesis, we design, implement and experiment with a multi-threaded parser for large polynomial expressions. We extract parallelism by splitting the input character string, into meaningful sub-strings that can be parsed concurrently before being merged into a single polynomial. Our implementation targeting multi-core processors is realized with the Basic Polynomial Algebra Subprograms (BPAS). Experimental results show that the approach is promising both in terms of speedup factors and memory consumption.

Summary for Lay Audience

Parsing large polynomial datasets is a time-consuming and computationally expensive process. In this thesis, we present a high-performance parallel parser that utilizes the front end compiler phase as its core operation. We will use lexical and semantic analysis programs, flex and bison, to automate the process. We apply data parallelism to concurrently parse split chunks of input sub-string in a multi-core processor. In conclusion, we gained significant speedup with lower memory footprints in parsing large polynomial datasets.

Download

Share

COinS