請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/2360完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳銘憲 | |
| dc.contributor.author | Ting-Kang Chang | en |
| dc.contributor.author | 張庭綱 | zh_TW |
| dc.date.accessioned | 2021-05-13T06:39:26Z | - |
| dc.date.available | 2017-08-24 | |
| dc.date.available | 2021-05-13T06:39:26Z | - |
| dc.date.copyright | 2017-08-24 | |
| dc.date.issued | 2017 | |
| dc.date.submitted | 2017-08-12 | |
| dc.identifier.citation | [1] Intel R Xeon R Processor E5-2620 v2 (15M Cache, 2.10 GHz) Product Specifications. https://ark.intel.com/products/75789/Intel-Xeon-Processor-E5-2620-v2-15M-Cache-2_10-GHz.
[2] Intel R 64 and IA-32 Architectures Optimization Reference Manual. https://software.intel.com/sites/default/files/managed/9e/bc/64-ia-32-architectures-optimization-manual.pdf, Jun 2017. [3] S. Chen and Q. Jin. Persistent b+-trees in non-volatile main memory. Proceedings of the VLDB Endowment, 8(7):786–797, 2015. [4] C. Diaconu, C. Freedman, E. Ismert, P.-A. Larson, P. Mittal, R. Stonecipher, N. Verma, and M. Zwilling. Hekaton: SQL server’s memory-optimized OLTP engine. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pages 1243–1254. ACM, 2013. [5] J. Huang, K. Schwan, and M. K. Qureshi. NVRAM-aware logging in transaction systems. Proceedings of the VLDB Endowment, 8(4):389–400, 2014. [6] A. Jaleel, K. B. Theobald, S. C. Steely Jr, and J. Emer. High performance cache replacement using re-reference interval prediction (RRIP). In ACM SIGARCH Computer Architecture News, volume 38, pages 60–71. ACM, 2010. [7] T. Karnagel, R. Dementiev, R. Rajwar, K. Lai, T. Legler, B. Schlegel, and W. Lehner. Improving in-memory database index performance with Intel R Transactional Synchronization Extensions. In High Performance Computer Architecture (HPCA), 2014 IEEE 20th International Symposium on, pages 476–487. IEEE, 2014. [8] C. Kim, D. Burger, and S. W. Keckler. An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches. In Acm Sigplan Notices, volume 37, pages 211–222. ACM, 2002. [9] H. Kimura. FOEDUS: OLTP engine for a thousand cores and NVRAM. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 691–706. ACM, 2015. [10] C. Lameter. Numa (non-uniform memory access): An overview. Queue, 11(7):40, 2013. [11] L. Lamport. Specifying concurrent program modules. ACM Transactions on Programming Languages and Systems (TOPLAS), 5(2):190–222, 1983. [12] V. Leis, A. Kemper, and T. Neumann. The adaptive radix tree: ARTful indexing for main-memory databases. In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 38–49. IEEE, 2013. [13] J. J. Levandoski, D. B. Lomet, and S. Sengupta. The Bw-Tree: A B-tree for new hardware platforms. In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 302–313. IEEE, 2013. [14] Z. Majo and T. R. Gross. Memory management in NUMA multicore systems: trapped between cache contention and interconnect overhead. In ACM SIGPLAN Notices, volume 46, pages 11–20. ACM, 2011. [15] S. Pelley, T. F. Wenisch, B. T. Gold, and B. Bridge. Storage management in the NVRAM era. Proceedings of the VLDB Endowment, 7(2):121–132, 2013. [16] S. Perarnau, M. Tchiboukdjian, and G. Huard. Controlling Cache Utilization of HPC Applications. In International Conference on Supercomputing (ICS), 2011. [17] H. Pirk, F. Funke, M. Grund, T. Neumann, U. Leser, S. Manegold, A. Kemper, and M. Kersten. CPU and cache efficient management of memory-resident databases. In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 14–25. IEEE, 2013. [18] H. Plattner and A. Zeier. In-memory data management: technology and applications. Springer Science & Business Media, 2012. [19] A. Scolari, D. B. Bartolini, and M. D. Santambrogio. A Software Cache Partitioning System for Hash-Based Caches. ACM Transactions on Architecture and Code Optimization (TACO), 13(4):57, 2016. [20] D. N. Simha, M. Lu, and T.-c. Chiueh. An update-aware storage system for lowlocality update-intensive workloads. In ACM SIGPLAN Notices, volume 47, pages 375–386. ACM, 2012. [21] L. Soares, D. Tam, and M. Stumm. Reducing the harmful effects of last-level cache polluters with an OS-level, software-only pollute buffer. In Proceedings of the 41st annual IEEE/ACM International Symposium on Microarchitecture, pages 258–269. IEEE Computer Society, 2008. [22] S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy transactions in multicore in-memory databases. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 18–32. ACM, 2013. [23] J. Yang, Q. Wei, C. Chen, C. Wang, K. L. Yong, and B. He. NV-Tree: Reducing Consistency Cost for NVM-based Single Level Systems. In FAST, volume 15, pages 167–181, 2015. [24] H. Zhang, G. Chen, B. C. Ooi, K.-L. Tan, and M. Zhang. In-memory big data management and processing: A survey. IEEE Transactions on Knowledge and Data Engineering, 27(7):1920–1948, 2015. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/2360 | - |
| dc.description.abstract | 低延遲、高流通量的記憶體式資料庫管理系統(DBMS)近年來因為硬體的發展，受到了研究與應用領域越來越多的關注。更甚者，有許多因應未來使用非揮發性隨機存取記憶體(NVRAM)之記憶體式儲存系統的研究也被提出。然而這些研究皆沒有對於在低局部性、密集的更新作業負載下的處理器快取利用率進行討論。此類負載容易造成低度的快取利用率，導致不理想的整體效能。我們設計了一個基於快取特性之批次更新架構藉以提升在此類負載下之效能。藉由將更新請求暫存於快取中，此系統可將數個於不同時間到達之相近請求聚合並在同一批次內更新，以避免對記憶體不必要的重複存取，進而減少快取未命中(Cache miss)並提升整體流通量。實驗結果顯示本論文提出的快取模型相對於未考量快取特性的參考模型，能節省最高達75%的末級快取(Last level cache)未命中數，以及達到最大65%的速度提升。 | zh_TW |
| dc.description.abstract | Low-latency, high throughput in-memory DBMSs have been attracting attention in research and application increasingly in recent years, thanks to hardware evolutions. Furthermore, there are many works proposed to address issues in the upcoming NVRAM era for durable in-memory storage. However, very few of them were focused on cache utilization for low-locality update-intensive workloads, which usually lead to poor cache utilization and undesirable performance. We design a cache-aware batch update model to improve cache efficiency for such workloads. By buffering update requests in cache, the system can aggregate spatially close requests arriving at distant time into one batched update, and avoid unnecessary data re-fetch from memory, thus reducing read latency and improve overall throughput. The experiments show that our proposed cache-aware model can save up to 75\% last-level-cache misses and achieve up to 1.65x speedup over a cache-oblivious reference model. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-13T06:39:26Z (GMT). No. of bitstreams: 1 ntu-106-R04921045-1.pdf: 2243015 bytes, checksum: 4255b405163eced5b999f62d40c799ad (MD5) Previous issue date: 2017 | en |
| dc.description.tableofcontents | 口試委員會審定書 i
Acknowledgments ii 中文摘要 iii Abstract iv 1 Introduction 1 2 Preliminaries 3 2.1 Batch Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Cache-Oblivious Data Update . . . . . . . . . . . . . . . . . . . . . . . 3 2.2.1 Distributed-Input Configuration . . . . . . . . . . . . . . . . . . 3 2.2.2 Cache interference . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.3 Memory bucket miss rate . . . . . . . . . . . . . . . . . . . . . . 4 3 Cache-Aware Batch Update 6 3.1 In-cache Batch Update . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.1 Batch aggregation ratio . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Relative Per-Request Misses . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Decoupled Threading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3.1 Lock-free threading . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3.2 Flushing request queues . . . . . . . . . . . . . . . . . . . . . . 10 4 Experiments & Discussions 11 4.1 Experiment Environment . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.1.1 NUMA effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.1.2 NUCA effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Experiment Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2.1 Data & request model . . . . . . . . . . . . . . . . . . . . . . . 12 4.2.2 Searching data structure . . . . . . . . . . . . . . . . . . . . . . 12 4.2.3 General factors settings . . . . . . . . . . . . . . . . . . . . . . . 13 4.3 Modeling the Cost per Input Request . . . . . . . . . . . . . . . . . . . . 13 4.4 Workload Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.4.1 Uniformly random . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.4.2 Clustered random . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.5 Cache Partition using Coloring . . . . . . . . . . . . . . . . . . . . . . . 15 4.5.1 Side effect of CControl . . . . . . . . . . . . . . . . . . . . . . . 15 4.6 Cache-Buckets Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.7 Overhead of Cache-Aware Model . . . . . . . . . . . . . . . . . . . . . 16 4.8 Changing memory Bucket Size . . . . . . . . . . . . . . . . . . . . . . . 17 4.9 Changing Effective Memory Bucket Number . . . . . . . . . . . . . . . 18 4.10 Relative LLC Miss Count . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.11 Summarization of All Factors . . . . . . . . . . . . . . . . . . . . . . . . 20 4.12 Improvement in Cost vs. Improvement in LLC-Misses . . . . . . . . . . 22 5 Conclusion 23 Bibliography 24 | |
| dc.language.iso | en | |
| dc.subject | 低局部性 | zh_TW |
| dc.subject | 記憶體式資料處理 | zh_TW |
| dc.subject | 快取記憶體 | zh_TW |
| dc.subject | low-locality | en |
| dc.subject | in-memory data processing | en |
| dc.subject | cache memory | en |
| dc.title | 基於快取特性之記憶體式資料庫批次更新 | zh_TW |
| dc.title | Cache-Aware Batch Update for In-Memory Databases | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 105-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 修丕承,黃仁暐,陳怡伶 | |
| dc.subject.keyword | 記憶體式資料處理,快取記憶體,低局部性, | zh_TW |
| dc.subject.keyword | in-memory data processing,cache memory,low-locality, | en |
| dc.relation.page | 26 | |
| dc.identifier.doi | 10.6342/NTU201701572 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2017-08-14 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-106-1.pdf | 2.19 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。