工作層級運算之資料庫快取

Abstract

這篇論文改進了工作層級運算(Job-Level computing)的效能。工作層級運算是一種通用的分散式運算，客戶端負責維護搜尋樹，並將搜尋過程分割為許多工作，交由現有的遊戲程式來計算。客戶端可以將搜尋樹儲存在記憶體中，但為了支援大規模的應用，如解出七路殺光圍棋、建造九路圍棋或六子棋的開局庫，我們使用資料庫來維護工作層級應用的搜尋樹。然而，當使用大量的運算支援時，存取資料庫所需的時間成為效能的瓶頸。這篇論文提出了適用於工作層級搜尋樹的快取機制，資料庫中儲存了完整的搜尋樹，透過在客戶端的記憶體中維護部分的搜尋樹來減少存取資料庫。我們的方法明顯地增進了存取效能。在不使用快取機制時，每秒可以執行8.96個工作操作，而使用快取時，可以執行167.88個工作操作，資料存取速度為原本的18倍。

This thesis improves upon Job-Level (JL) computing, a general distributed computing approach. In JL computing, a client maintains the overall search tree and encapsulates the overall search into coarse-grained jobs, which are then each calculated by pre-existing game-playing programs. In order to support large-scale problems such as solving 7x7 killall-Go, or building opening books for 9x9 Go or Connect6, JL computing is modified so that the entire search tree is stored in a database, as opposed to simply being stored in the client process’ memory. However, the time cost of accessing this database becomes a bottleneck on performance when using a large number of computing resources. This thesis proposes a cache mechanism for JL search trees. Instead of the previous approach, where the entire search tree is stored in the database, we maintain parts of the search tree in the memory of the client process to reduce the number of database accesses. Our method significantly improves the performance of job operations. We can perform 8.96 jobs/second on average without using the cache mechanism (not taking into consideration the job execution time). With the cache mechanism, the same application can perform up to 167.88 jobs/second. The data access speed is 18 times faster of the original approach when using the cache mechanism.