DC Field | Value | Language |
---|---|---|
dc.contributor.author | 김성환 | - |
dc.date.accessioned | 2022-03-29T02:53:23Z | - |
dc.date.available | 2022-03-29T02:53:23Z | - |
dc.date.issued | 2020 | - |
dc.identifier.other | OAK-2015-08328 | - |
dc.identifier.uri | http://postech.dcollection.net/common/orgView/200000336011 | ko_KR |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/111133 | - |
dc.description | Doctor | - |
dc.description.abstract | This dissertation studies the optimization of list intersection, as a fundamental building block of search engine. Though modern architectures contribute to expedite predictable data accesses, by using caching, hardware prefetching and vectorization, accelerating list intersection is impaired by non-contiguous memory accesses and control-flow divergence, which we name as two bottlenecks for list intersection - memory latency and branch misprediction penalty respectively. To overcome this phenomenon, dissertation proposes the following two contributions. First, we identify the magnitude of impacts for the two bottlenecks on the execution of state-of-the-art list intersection algorithms, then propose a cost-based optimization methodology by generating a cost model of a state-of-the-art algorithm with very high accuracy. Second, we propose new data structures and algorithms that break the identified bottlenecks. The proposed data structure improves cache efficiency by replacing several random accesses with sequential scan, and each proposed algorithm offers various parallel optimization methods such as branchless computation, software pipelining, and software prefetching. | - |
dc.language | eng | - |
dc.publisher | 포항공과대학교 | - |
dc.title | Hardware-aware Optimization of List Intersection in Web Search | - |
dc.title.alternative | 하드웨어를 고려한 웹 검색에서의 목록 교차 연산 최적화 | - |
dc.type | Thesis | - |
dc.contributor.college | 일반대학원 컴퓨터공학과 | - |
dc.date.degree | 2020- 8 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.