Date of Completion

11-14-2017

Embargo Period

11-14-2017

Advisors

Omer Khan, Marten van Dijk, John Chandy

Field of Study

Electrical Engineering

Degree

Master of Science

Open Access

Open Access

Abstract

Graph algorithms have gained popularity and are utilized in high performance and mobile computing paradigms. Input dependence due to input graph changes leads to performance variations in such algorithms. The impact of input dependence for graph algorithms is not well studied in the context of approximate computing. This thesis conducts such analysis by applying loop perforation, which is a general approximation mechanism that transforms the program loops to drop a subset of their total iterations. The analysis identifies the need to adapt the inner and outer loop perforation as a function of input graph characteristics, such as the density or size of the graph. A predictive model is proposed to learn the near-optimal loop perforation rates using synthetic input graphs. When the input-aware loop perforation model is applied to real world graphs, the evaluated graph algorithms systematically degrade accuracy to achieve performance and power benefits. Results show ~30% performance and ~19% power utilization improvements on average at a program accuracy loss threshold of 10% for an NVidia GPU. The analysis is also conducted for two concurrent Intel CPU architectures, an 8-core Xeon and a 61-core Xeon Phi machine.

Major Advisor

Omer Khan

Download

Share

COinS