| 中畑 裕 | 1651202: M, 1回目発表 | 大規模システム管理 笠原 正治 |
|
title: Enumerating Graph Partitions for Evacuation Planning using ZDDs
abstract: In evacuation planning, we have to assign each shelter to each district. It is important to minimize evacuation time and avoid the cross of evacuees' trajectories. However, there are many patterns of assignment, so it is difficult to find a good assignment. In this study, we regard the assignment of shelters to districts as a graph partitioning problem, and propose an algorithm to enumerate partitions satisfying constraints using a data structure Zero-suppressed Binary Decision Diagram (ZDD). language of the presentation: Japanese 発表題目:ZDDを用いた避難所割り当てのためのグラフ分割の列挙 発表概要:避難計画において、地区ごとに避難先となる避難所を割り当てる必要がある。この際、各地区から避難所までの距離が小さいことや、避難者の動線の交差を避けるようにグループを作ることが重要である。しかし割り当てのパターンは膨大であり、それらの中から適切な割り当てを見つけることは難しい。本研究では、避難所割り当て問題をグラフの連結成分分割とみなし、条件を満たす連結成分分割を Zero-suppressed Binary Decision Diagram(ZDD) と呼ばれるデータ構造を用いて効率的に列挙する手法を提案する。 | ||
| APICHANUKUL WORACHATE | 1551201: M, 2回目発表 | 大規模システム管理 笠原 正治, 飯田 元, 笹部 昌弘, 川原 純 |
|
title: An elaborate task distribution algorithm for solving the problem of stragglers in Hadoop.
abstract: Apache Hadoop is a distributed computing platform that has been adopted to use in many famous companies such as Facebook, Yahoo and Amazon. Similar to other platforms, Hadoop is confronted with a well-known problem in distributed computing areas called the issue of stragglers in which some tasks of a job take unusual long execution time and delay the completion time of the job. The slow tasks are called straggler tasks. Hadoop provides a speculative algorithm to treat the problem, but the default speculative algorithm returns low performance to classify straggler tasks. We propose an improved version of speculative algorithm, which is called Accuracy Improvement for Backup Task (AIBT), to accurately detect straggler tasks. Although the problem is better relieved by AIBT, it still exists. We have found that an inefficient task distribution in existing scheduling algorithms is a cause of the straggler problem. Existing algorithms neglect to take care of the utilization level of each node when they distribute tasks. As a result, some nodes are over utilized and suffer from the straggler problem. Therefore, we propose a new scheduling algorithm which effectively distributes tasks to be executed on suitable nodes. To extract the suitable nodes, our approach uses a cost function which takes both utilization level of each node and location of processed data into account. We evaluate our algorithm by performing an experiment in an actual Hadoop environment. Numerical results show that our approach not only solves the straggler problem, but also reduces task execution time and increases the amount of local execution compared with the existing scheduling algorithms. language of the presentation: English | ||