Computing with unreliable resources : design, analysis and algorithms
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/89846 |
| _version_ | 1826194500708466688 |
|---|---|
| author | Wang, Da, Ph. D. Massachusetts Institute of Technology |
| author2 | Gregory W. Wornell. |
| author_facet | Gregory W. Wornell. Wang, Da, Ph. D. Massachusetts Institute of Technology |
| author_sort | Wang, Da, Ph. D. Massachusetts Institute of Technology |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. |
| first_indexed | 2024-09-23T09:57:04Z |
| format | Thesis |
| id | mit-1721.1/89846 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:57:04Z |
| publishDate | 2014 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/898462019-04-12T15:03:33Z Computing with unreliable resources : design, analysis and algorithms Wang, Da, Ph. D. Massachusetts Institute of Technology Gregory W. Wornell. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 187-197) and index. This thesis is devoted to the study of computing with unreliable resources, a paradigm emerging in a variety of technologies, such as circuit design, cloud computing, and crowdsourcing. In circuit design, as we approach the physical limits, semiconductor fabrication has been increasingly susceptible to fabrication flaws, resulting unreliable circuit components. In cloud computing, due to co-hosting, virtualization and other factors, the response time of computing nodes are variable. This calls for computation frameworks that take this unreliable quality-of-service into account. In crowdsourcing, we humans are the unreliable computing processors due to our inherent cognitive limitations. We investigate these three topics in the three parts of this thesis. We demonstrate that it is often necessary to introduce redundancy to achieve reliable computing, and this needs to be carried out judiciously to attain an appealing balance between reliability and resource usage. In particular, it is crucial to take the statistical properties of unreliability into account during system design, rather than to handle it as an afterthought. In the first part, we investigate the topic of circuit design with unreliable circuit components. We first analyze the design of Flash Analog-to-Digital Converter (ADC) with imprecise comparators. Formulating this as a problem of scalar quantization with noisy partition points, we analyze fundamental limits on ADC accuracy and obtain designs that increase the yield of ADC (e.g., 5% to 10% for 6-bit Flash ADCs). Our results show that, given a fixed amount of silicon area, building more smaller and less precise comparators leads to better ADC accuracy. We then address the problem of digital circuit design with faulty components. To achieve reliability, we introduce redundant elements that can replace faulty elements via a configurable interconnect. We show that the required number of redundant elements depends on the amount of interconnect available, and propose designs that achieve near-optimal trade-o between redundancy and interconnect overhead in several design settings. The second part of this thesis explores the problem of executing a collection of tasks in parallel on a group of computing nodes. This setting is often seen in cloud computing and crowdsourcing, where the response times of computing nodes are random due to their variability. In this case, the overall latency is determined by the response time of the slowest computing node, which is often much larger than the average response time. Task replication, which sends the same task to multiple computing nodes and obtains the earliest result, reduces latency, but in general incurs additional resource usage. We propose a theoretical framework to analyze the trade-o between latency and resource usage. We show that, while in general there is a tension between latency and resource usage, there exist scenarios where replicating tasks judiciously reduce both latency and resource usage simultaneously. Our investigation gives insights on when and how replication helps, and provides ecient scheduling policies for a variety of computing scenarios. Lastly, we research the problem of crowd-based ranking via pairwise comparisons, with humans as unreliable comparators. We formulate this as the problem of approximate sorting with noisy comparisons. By developing a rate-distortion theory on permutation spaces, we obtain information-theoretic lower bounds for the query complexity of approximate sorting with both noiseless and noisy comparisons. Our lower bound shows the optimality of certain existing algorithms with respect to noiseless comparisons and provides a benchmark for approximate sorting with noisy comparisons. by Da Wang. Ph. D. 2014-09-19T19:37:11Z 2014-09-19T19:37:11Z 2014 2014 Thesis http://hdl.handle.net/1721.1/89846 890133085 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 197 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Wang, Da, Ph. D. Massachusetts Institute of Technology Computing with unreliable resources : design, analysis and algorithms |
| title | Computing with unreliable resources : design, analysis and algorithms |
| title_full | Computing with unreliable resources : design, analysis and algorithms |
| title_fullStr | Computing with unreliable resources : design, analysis and algorithms |
| title_full_unstemmed | Computing with unreliable resources : design, analysis and algorithms |
| title_short | Computing with unreliable resources : design, analysis and algorithms |
| title_sort | computing with unreliable resources design analysis and algorithms |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/89846 |
| work_keys_str_mv | AT wangdaphdmassachusettsinstituteoftechnology computingwithunreliableresourcesdesignanalysisandalgorithms |