| dc.identifier.uri | http://hdl.handle.net/11401/77236 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dc.type | Dissertation | |
| dcterms.abstract | This dissertation is an excursion into computer-discovered algorithms and computer-aided algorithm design. In our vision of the not-so-distant future of computing, machines will take the responsibility of designing and implementing most, if not all, machine-specific highly efficient nontrivial algorithms with provable correctness and performance guarantees. Indeed, as the complexity of computing hardware grows and their basic architectures keep changing rapidly, manually redesigning and reimplementing key algorithms for high performance on every new architecture is quickly becoming an impossible task. Automation is needed. We design algorithms that can design other algorithms. Our focus is on auto-generating algorithms for solving dynamic programming (DP) recurrences efficiently on state-of-the-art parallel computing hardware. While DP recurrences can be solved very easily using nested or even tiled nested loops, for high performance on modern processors/coprocessors with cache hierarchies, portability across machines, and automatic adaptivity to runtime fluctuations in the availability of shared resources (e.g., cache space) highly nontrivial recursive divide-and-conquer algorithms are needed. But, these recursive divide-and-conquer algorithms are difficult to design and notoriously hard to implement for high performance. Furthermore, new DP recurrences are being encountered by scientists every day for solving brand new problems in diverse application areas ranging from economics to computational biology. But, how does an economist or a biologist without any formal training in computer science design an efficient algorithm for evaluating his/her DP recurrence on a computer? Well, we can help! We present Autogen -- an algorithm that given any blackbox implementation of a DP recurrence (e.g., inefficient naive serial loops) from a wide class of DP problems, can automatically discover a fast recursive divide-and-conquer algorithm for solving that problem on a shared-memory multicore machine. We mathematically formalize Autogen, prove its correctness, and provide theoretical performance guarantees for the auto-discovered algorithms. These auto-generated algorithms are shown to be efficient (e.g., highly parallel with highly optimizable kernels, and cache-, energy-, and bandwidth-efficient), portable (i.e., cache- and processor-oblivious), and robust (i.e., cache- and processor-adaptive). We present Autogen-Wave -- a framework for computer-assisted discovery of fast divide-and-conquer wavefront versions of the algorithms already generated by Autogen. These recursive wavefront algorithms retain all advantages of the Autogen-discovered algorithms on which they are based, but have better and near-optimal parallelism due to the wavefront order of execution. We also show how to schedule these algorithms with provable performance guarantees on multicore machines. We present Viterbi -- an efficient cache-oblivious parallel algorithm to solve the Viterbi recurrence, as a first step toward extending Autogen to handle DP recurrences with irregular data-dependent dependencies. Our algorithm beats the current fastest Viterbi algorithm in both theory and practice. We present Autogen-Tile -- a framework for computer-aided design of high-performing and easily portable recursively tiled/blocked algorithms for a wide class of DP problems having fractal-type dependencies. These recursively tiled algorithms have excellent cache locality and excellent parallel running time on multi-/many-core machines with deep memory hierarchy. We present Autogen-Tradeoff -- a framework that can be used to design efficient and portable not-in-place algorithms to asymptotically increase the parallelism of some of the Autogen-discovered algorithms without affecting cache-efficiency. This dissertation takes the first major step on which to build computing systems for automatically designing efficient and portable nontrivial algorithms. We hope that more work follows in this science of algorithm discovery. | |
| dcterms.available | 2017-09-20T16:52:15Z | |
| dcterms.contributor | Chowdhury, Rezaul | en_US |
| dcterms.contributor | Bender, Michael A | en_US |
| dcterms.contributor | Liu, Yanhong A | en_US |
| dcterms.contributor | Chapman, Barbara | en_US |
| dcterms.contributor | Agrawal, Kunal . | en_US |
| dcterms.creator | Ganapathi, Pramod | |
| dcterms.dateAccepted | 2017-09-20T16:52:15Z | |
| dcterms.dateSubmitted | 2017-09-20T16:52:15Z | |
| dcterms.description | Department of Computer Science | en_US |
| dcterms.extent | 257 pg. | en_US |
| dcterms.format | Application/PDF | en_US |
| dcterms.format | Monograph | |
| dcterms.identifier | http://hdl.handle.net/11401/77236 | |
| dcterms.issued | 2016-12-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2017-09-20T16:52:15Z (GMT). No. of bitstreams: 1
Ganapathi_grad.sunysb_0771E_13157.pdf: 14198231 bytes, checksum: 55edb4e15c99fee94f9a90cd83fc7582 (MD5)
Previous issue date: 1 | en |
| dcterms.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dcterms.subject | Automatic Discovery, Automatic Generation, Cache-Oblivious, Divide-and-Conquer, Dynamic Programming, Parallel | |
| dcterms.subject | Computer science | |
| dcterms.title | Automatic Discovery of Efficient Divide-&-Conquer Algorithms for Dynamic Programming Problems | |
| dcterms.type | Dissertation | |
