UTokyo Repository 東京大学

UTokyo Repository >
124 情報理工学系研究科 >
40 電子情報学専攻 >
1244025 修士論文(電子情報学専攻) >

このページ(論文)をリンクする場合は次のURLを使用してください: http://hdl.handle.net/2261/28050

タイトル: A High-performance Deadlock-free Overlay for Wide-area Parallel and Distributed Programming
その他のタイトル: 広域並列分散プログラミングのための高性能デッドロックフリーオーバレイ
著者: Hironaka, Ken
著者(別言語): 弘中, 健
発行日: 2009年3月31日
抄録: Parallel and distributed computing in Wide-area environments is complicated by connectivity issues like NATs/firewalls, and dynamic changes in the available resources. Therefore, programming in these environments requires substantial support from programming frameworks. Such frameworks can help resolve low-level concerns while providing abstractions to implement applications more easily. Meanwhile overlay networks, which create their own network on top of the internet using UDP/TCP links, have become popular communication mediums for frameworks in these environments as they transparently enable communication even in wide-area networks. Thus, high-performance overlays are crucial in this context. This paper presents one such programming framework and a high-performance overlay whose goal is to serve as its communication layer./ The first proposal designs and implements an overlay-based programming framework for largescale wide-area computing by minimally extending distributed object-oriented models for maximum generality and flexibility. Aside from introducing constructs to facilitate parallel computation and to handle runtime process joins/leaves, the framework automatically creates and manages an overlay to enable communication across WANs with minimal user intervention. In the framework, parallelism is expressed via asynchronous method invocations to distributed objects for a natural transition from sequential programs. To make parallelism manageable, the framework introduces an implicit serialization semantics on objects to relieve programmers from explicit synchronization, while avoiding deadlock problems. In the implementation, participating nodes automatically construct an overlay, and relieve the users from manual configuration and managing the overlay as it dynamically changes during the computation. This framework, gluepy is implemented as a library for Python to allow rapid development of complex workflows and to maximally leverage the richness of its libraries. For evaluation, this work shows, on over 900 cores across 9 clusters with complex networks (involving NATs and firewalls), how applications with dynamic node joins/failures can be expressed simply and executed easily./ The second proposal presents the design and implementation of a high-performance overlay network that attains the throughput performance of the underlying wide-area network. The addressed core issue is a flow control problem where intermediate overlay nodes have limited buffer memory, while the forwarding must yield full network throughput exceeding Gbps. Implementing a naive flow control, however can deadlock the overlay. The proposed overlay presents a deadlock-free overlay that couples TCP connections and fixed intermediate buffer memory. The method fully takes advantage of TCP’s flow control and implements a simple flow control scheme by creating dependencies among connections in an overlay path. Meanwhile, the proposal adapts a deadlock-free routing algorithm forheterogeneous wide-area networks, so deadlocks among communication can be avoided without sacrificing performance. The proposal also incorporates overlay construction and routing optimizations that account for underlying network latency and bandwidth information. This work demonstrates, via simulation on 13 clusters (515 nodes) and by evaluation on 7 clusters (170 nodes), that the proposed deadlock-free routing poses negligible overhead in comparison to deadlock-unaware routing, and comparably with direct communication. It further demonstrates that for certain collective communications, the proposed overlay even out-performs direct communication by mitigating or completely avoiding network contention. This is shown on systems ranging from a single-switch cluster with 36 nodes to a Grid environment with 4 clusters and 291 nodes.
内容記述: 報告番号: ; 学位授与年月日: 2009-03-31 ; 学位の種別: 修士 ; 学位の種類: 修士(工学) ; 学位記番号: ; 研究科・専攻: 情報理工学系研究科電子情報学専攻
URI: http://hdl.handle.net/2261/28050
出現カテゴリ:1244025 修士論文(電子情報学専攻)
025 修士論文


ファイル 記述 サイズフォーマット
hironaka.pdf1.34 MBAdobe PDF見る/開く



Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - ご意見をお寄せください