Graduate Thesis Or Dissertation
 

The dynamic speculation and performance prediction of parallel loops

公开 Deposited

可下载的内容

下载PDF文件
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/z890rw34f

Descriptions

Attribute NameValues
Creator
Abstract
  • General purpose computer systems have seen increased performance potential through the parallel processing capabilities of multicore processors. Yet this potential performance can only be attained through parallel applications, thus forcing software developers to rethink how everyday applications are designed. The most readily form of Thread Level Parallelism (TLP) within any program are from loops. Unfortunately, the majority of loops cannot be easily multithreaded due to inter-iteration dependencies, conditional statements, nested functions, and dynamic memory allocation. This dissertation seeks to understand the fundamental characteristics and relationships of loops in order to assist programmers and compilers in exploiting TLP. First, this dissertation explores a hardware solution that exploits (TLP) through Dynamic Speculative Multithreading (D-SpMT), which can extract multiple threads from a sequential program without compiler support or instruction set extensions. This dissertation presents Cascadia, a D-SpMT multicore architecture that provides multi-grain thread-level support. Cascadia applies a unique sustainable IPC (sIPC) metric on a comprehensive loop tree to select the best performing nested loop level to multithread. Results showed that Cascadia can extract large amounts of TLP, but ultimately, only yielded moderate performance gains. The lack of overall performance gains exhibited by Cascadia were due to the sequential nature of applications, rather than Cascadia's ability to perform D-SpMT. In order to fully exploit TLP through loops, some loop level analysis and transformation must first be performed. Therefore, second contribution of this dissertation is the development of several theoretical methodologies to aid programmers and auto-tuners in parallelizing loops. This work found that the inter-iteration dependencies have a two-fold effect on the loop's parallel performance. First, the performance is primarily affected by a single, dominant dependency, and it is the execution of the dominant dependency path that directly determines the parallel performance of the loop. Any additional dependencies cause a secondary effect that may increase the execution time due to relative dependency path differences. Furthermore, this study analyzes the effects of non-ideal conditions, such as a limited number of processors, multithreading overhead, and irregular loop structures.
License
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
权利声明
Publisher
Peer Reviewed
Language
Replaces

关联

Parents:

This work has no parents.

属于 Collection:

单件

缩略图 标题 上传日期 公开度 行动
file details zier_osu_dissertation_2009.pdf 2017-08-01 公开 下载