研究者詳細 - 八杉　昌宏

論文 - 八杉　昌宏

分割表示78 件中 1 - 20 件目／全件表示 >>

HOPE: A Parallel Execution Model Based on Hierarchical Omission 査読有り国際誌

Masahiro Yasugi, Daisuke Muraoka, Tasuku Hiraishi, Seiji Umatani, Kento Emoto

Proceedings of the 48th International Conference on Parallel Processing (ICPP 2019) 77:1 - 77:11 2019年08月

担当区分：責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Kyoto 2019年08月05日 - 2019年08月08日

© 2019 ACM. This paper presents a new approach to fault-tolerant language systems without a single point of failure for irregular parallel applications. Work-stealing frameworks provide good load balancing for many parallel applications, including irregular ones written in a divide-and-conquer style. However, work-stealing frameworks with fault-tolerant features such as checkpointing do not always work well. This paper proposes a completely opposite "work omission" paradigm and its more detailed concept as a "hierarchical omission"-based parallel execution model called HOPE. HOPE programmers' task is to specify which regions in imperative code can be executed in sequential but arbitrary order and how their partial results can be accessed. HOPE workers spawn no tasks/threads at all; rather, every worker has the entire work of the program with its own planned execution order, and then the workers and the underlying message mediation systems automatically exchange partial results to omit hierarchical subcomputations. Even with fault tolerance, the HOPE framework provides parallel speedups for many parallel applications, including irregular ones.

DOI： 10.1145/3337821.3337899

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85071139641&origin=inward

A Coherent Random Number Utilization Scheme for a Fault-tolerant Parallel Execution Model Based on Hierarchical Omission 査読有り

Shogo Hiromatsu, Masahiro Yasugi, Tasuku Hiraishi, Kento Emoto

Journal of Information Processing ( 一般社団法人情報処理学会 ) 33 ( 0 ) 295 - 311 2025年04月

担当区分：責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

High productivity, scalability, load balancing, and fault tolerance are all important issues of massively parallel computing. A parallel execution model called HOPE, which we are proposing, addresses these issues by “hierarchical omission of redundant computations”. Every HOPE worker performs the entire divide-and-conquer computation with its own planned order, whereas it can omit subcomputations whose results are obtained from other workers at runtime, achieving fault tolerance and parallel efficiency as a team of workers. In most random number generation algorithms, a random number is generated on the basis of the internal state after the previous random number generation. Therefore, simple reordering does not preserve coherent results/conditions among workers based on the properties of utilized random numbers. In order to always use the same sequence for each hierarchical subcomputation, this study explores coherent random number utilization schemes, using Sobol' sequences or the PCG random number generator, which allow generation starting from the latter part by skipping the first part. In addition, the Monte Carlo method is an important application of random numbers. In this study, we examine a HOPE application that computes highly dimensional numerical integrals for pricing securities known as MBS (mortgage-backed securities) using the Monte Carlo method, where the convergence speed of integration errors is independent of dimensionality.

DOI： 10.2197/ipsjjip.33.295

Designing Restartable Exception Handling Mechanisms for Implementing Efficient and Safe High-level Languages 査読有り

Masahiro Yasugi, Kento Emoto, Tasuku Hiraishi

Journal of Information Processing ( 一般社団法人情報処理学会 ) 32 ( 0 ) 436 - 450 2024年05月

担当区分：筆頭著者,　責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

Mechanisms for legitimate execution stack access (LESA for short) provide legitimate access to values of callers’ variables sleeping deeply in a C-like execution stack. LESA mechanisms enable efficient implementations of high-level services that require dynamic rearrangement of running software, such as garbage collection, first-class continuations, and dynamic load balancing, for implementing efficient and safe high-level languages. As a nestedfunction-style LESA mechanism, we can create a closure from a nested function definition and indirectly call the nested function via a pointer to the closure, achieving access to values of the variables captured in the closure-creationtime environment. In this study, we propose restartable exception handling mechanisms as new LESA mechanisms, which provide callable exception handlers without non-local exiting; handlers are found on the basis of dynamic scope without requiring pointers. In addition, the LESA mechanisms can be used at multiple levels; e.g., garbage collection can be started during the creation of a first-class continuation. In this paper, we design core languages that feature leveled restartable exception handling mechanisms and discuss their properties and implementations.

DOI： 10.2197/ipsjjip.32.436

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85195605010&origin=inward

Portable Implementations of Work Stealing 査読有り国際誌

Masahiro Yasugi, Tasuku Hiraishi, Chihiro Takeuchi

Proceedings of International Conference on High Performance Computing in Asia-Pacific Region (HPCAsia 2024) 12 - 22 2024年01月

担当区分：筆頭著者,　責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Japan Nagoya 2024年01月25日 - 2024年01月27日

Work stealing is a well-known technique for dynamic load balancing; however, manually writing work-stealing protocols is error-prone. We can use the Tascell parallel programming language for the correct and portable implementation of work stealing; the implementation combines polling and adequate mutual exclusion. In Tascell, we can express on-demand concurrency for backtracking-based load balancing where a worker performs a sequential computation with its own execution stack unless it is requested to spawn a task. To spawn a larger task by temporarily backtracking, nested functions can be used for legitimate execution stack access. As nested functions for extended C languages, we can use GCC's heavyweight implementation with runtime code generation or lightweight implementations by enhancing GCC; however, compiler-based implementations are poor in portability. In this study, we implement and evaluate more portable Tascell frameworks called "Tascell/SC"by using transformation-based portable implementations of nested functions. In addition, we propose Tascell-inspired portable frameworks only in C++ called "Tascell++"by using lambda expressions in C++11 for legitimate execution stack access.

DOI： 10.1145/3635035.3635041

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85184360040&origin=inward

Evaluating and Analyzing Irregular Tree Search in the Tascell and HOPE Parallel Programming Languages 査読有り国際誌

Yusuke Shiki, Masahiro Yasugi, Tasuku Hiraishi

Post-proceedings of the 23rd International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2022) 13798 LNCS 262 - 272 2023年04月

担当区分：責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Sendai 2022年12月07日 - 2022年12月09日

Well-designed parallel programming languages are useful for safely parallelizing irregular tree search. The Tascell language can speed up a tree search with work stealing; every Tascell worker mostly performs a computation sequentially, promoting long-term sequential (re)use of workspaces. We comprehensively examine techniques for reusing a workspace among siblings of a depth-first search, sequential update of a single partial solution in a backtracking search, and direct merging of search results. The HOPE fault-tolerant language can also speed up a tree search; every HOPE worker executes the entire computation redundantly and sequentially in its own planned order and exchanges partial results sophisticatedly at runtime to omit redundant subcomputations. For HOPE, we propose an adaptive workspace-sharing technique for unmerged distinct search results. In this study, we evaluate and analyze individual techniques by using the UTS benchmark and multiple backtracking search algorithms, optionally combined with histogram generation; Tascell and HOPE show better performance than Cilk Plus and OpenMP.

DOI： 10.1007/978-3-031-29927-8_21

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85159423932&origin=inward

Construction of Hierarchical Matrix on Distributed Memory Systems using a Task Parallel Language 査読有り国際誌

Zhengyang Bai, Tasuku Hiraishi, Akihiro Ida, Masahiro Yasugi, Keiichiro Fukazawa

Proceedings of the 10th International Symposium on Computing and Networking Workshops (CANDARW 2022) (10th International Workshop on Computer Systems and Architectures CSA 2022, held in conjunction with CANDAR 2022) 48 - 54 2023年03月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Himeji 2022年11月21日 - 2022年11月24日

A hierarchical matrix is an approximated form of the dense matrix that represents the N-by-N correlations of N objects. The construction of the hierarchical matrix is achieved by dividing a matrix into submatrices (partitioning), followed by calculating these submatrices' entries (filling). The matrix partitioning is divided into two sub-steps: cluster tree (CT) construction by dividing objects into clusters, hierarchically, and block cluster tree (BCT) construction by observing all cluster pairs at the same level of the cluster tree that satisfy a given admissibility condition. We can apply task parallelism to filling by treating each submatrix as a parallelization unit. In existing implementations, the partitioning is redundantly executed on every computing node, and filling is executed in parallel by assigning a set of tasks to each worker statically. However, we cannot get good load balance using such implementations because it is difficult to predict the workload of each task precisely. In this paper, we propose a new parallel implementation of the hierarchical matrix construction, where a BCT construction is executed in parallel using all workers of all computing nodes. When a worker finds a BCT leaf during BCT construction, it executes filling for the submatrix corresponding to the leaf. To get good load balance, we parallelized the BCT construction using the task parallel language Tascell, which enables easy and efficient parallelization of tree recursive algorithms by employing a dynamic load balancing strategy. In numerical experiments with 3D electric field analyses using up to 16 computing nodes each of which has 36 cores, our implementation achieved up to 1.9-fold speedups compared to an implementation using the static task assignment strategy.

DOI： 10.1109/CANDARW57323.2022.00058

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85158858235&origin=inward

Parallelization of Matrix Partitioning in Hierarchical Matrix Construction on Distributed Memory Systems 査読有り

Zhengyang Bai, Tasuku Hiraishi, Akihiro Ida, Masahiro Yasugi

Journal of Information Processing ( 一般社団法人情報処理学会 ) 30 ( 0 ) 742 - 754 2022年10月

記述言語：英語掲載種別：研究論文（学術雑誌）

A hierarchical matrix (H-matrix) is an approximated form that represents N × N correlations of N objects. H-matrix construction is achieved by dividing a matrix into submatrices (partitioning), followed by calculating these submatrices' element values (filling). Matrix partitioning consists of two steps: cluster tree (CT) construction, where objects are divided into clusters hierarchically; and block cluster tree (BCT) construction, which involves observing all cluster pairs at the same CT level that satisfies the admissibility condition. This study proposes two parallel implementation methods of partitioning operations on distributed memory systems (DMSs): distributed cluster tree construction (DCTC) and redundant cluster tree construction (RCTC). In DCTC, both CT and BCT constructions are parallelized using workers in all computing nodes. In RCTC, CT is constructed in every computing node redundantly by employing only intra-node work stealing. The BCT is then constructed in parallel using workers in all computing nodes. RCTC cannot achieve speedup using multiple computing nodes, but can eliminate the data exchange cost incurred by DCTC. We used the task-parallel language Tascell, which employs both intra- and inter-node work stealing, to handle arbitrary unbalanced tree construction and traversal on DMSs. Our RCTC implementations achieved a 1.11-1.20-fold speedup using up to 8 nodes × 36 workers in numerical experiments with 3D electric field analyses and N ≃ 108.

DOI： 10.2197/ipsjjip.30.742

Scopus

CiNii Research

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85139909867&origin=inward

Work-stealing Strategies That Consider Work Amount and Hierarchy 査読有り

Ryusuke Nakashima, Masahiro Yasugi, Hiroshi Yoritaka, Tasuku Hiraishi, Seiji Umatani

Journal of Information Processing ( 一般社団法人情報処理学会 ) 29 478 - 489 2021年07月

担当区分：責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

This paper proposes work-stealing strategies for an idle worker (thief) to select a victim worker. These strategies avoid small tasks being stolen to reduce the total task-division cost. We implemented these strategies on a work-stealing framework called Tascell. First, we propose new types of priority- and weight-based steal strategies. Programmers can let each worker estimate and declare, as a real number, the amount of remaining work required to complete its current task so that declared values are used as "priorities" or "weights". With a priority-based strategy, a thief selects the victim that has the highest known priority at that time. With a weight-based non-uniformly random strategy, a thief uses the relative weights of victim candidates as their selection probabilities. Second, we propose work-stealing strategies to alleviate excessive intra-node work stealing and excessive "steal backs" (or leapfroggings); for example, we allow workers to steal tasks from external nodes with some frequency even if work remains inside the current node. Our evaluation uses a parallel implementation of the "highly serial" version of the Barnes-Hut force-calculation algorithm in a shared memory environment and five benchmark programs in a distributed memory environment.

DOI： 10.2197/ipsjjip.29.478

CiNii Article

その他リンク： https://ci.nii.ac.jp/naid/130008065250

Parallelization of Matrix Partitioning in Construction of Hierarchical Matrices using Task Parallel Languages 査読有り

Zhengyang Bai, Tasuku Hiraishi, Hiroshi Nakashima, Akihiro Ida, Masahiro Yasugi

Journal of Information Processing ( 一般社団法人情報処理学会 ) 27 840 - 851 2019年12月

記述言語：英語掲載種別：研究論文（学術雑誌）

© 2019 Information Proessing Soiety of Japan. A hierarchical matrix (H-matrix) is an approximated form that represents N × N correlations of N objects. H-matrix construction is achieved by partitioning a matrix into submatrices, followed by calculating the element values of these submatrices. This paper proposes implementations of matrix partitioning using task parallel languages, Cilk Plus and Tascell. Matrix partitioning is divided into two steps: cluster tree construction by dividing objects into clusters hierarchically, and block cluster tree construction by observing all cluster pairs at the same level of the cluster tree that satisfy an admissibility condition. As the two types of trees constructed and traversed in these steps are un-predictably unbalanced, it is expected that we can efficiently parallelize both these steps using task parallel languages. To obtain sufficient parallelism in the cluster tree construction, we not only execute recursive calls in parallel but also parallelize the inside of each recursive step. For the block cluster tree construction, we assigned each worker its own space so that the workers can store the cluster pairs without using locks. As a result, compared to a sequential implementation in C, we achieved up to an 11.5-fold speedup using Cilk Plus and a 12.6-fold speedup by Tascell for the cluster tree construction. For the block cluster tree construction, up to a 37.7-fold speedup by Cilk Plus and a 38.8-fold speedup using Tascell are achieved. In regard to the entire process of matrix partitioning, we achieved up to a 12.2-fold speedup by Cilk Plus and a 14.5-fold speedup using Tascell. All experiments were executed on two 18-core Xeon processors with real datasets to generate coefficient matrices used in the surface charge method.

DOI： 10.2197/ipsjjip.27.840

Scopus

CiNii Article

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85078518192&origin=inward

Extending a Work-Stealing Framework with Priorities and Weights 査読有り国際誌

Ryusuke Nakashima, Hiroshi Yoritaka, Masahiro Yasugi, Tasuku Hiraishi, Seiji Umatani

Proceedings of the 9th Workshop on Irregular Applications: Architectures and Algorithms (IA3 2019) (held in conjunction with SC 2019) 9 - 16 2019年11月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

USA Denver 2019年11月18日 - 2019年11月18日

© 2019 IEEE. This paper proposes priority-based and weight-based steal strategies for an idle worker (thief) to select a victim worker in work-stealing frameworks. Typical work-stealing frameworks employ uniformly random victim selection. We implemented the proposed strategies on a work-stealing framework called Tascell; Tascell programmers can let each worker estimate and declare the remaining work amount of its current task as a real number so that the enhanced Tascell framework can use declared values as priorities or weights. To reduce the total task division cost, the proposed strategies avoid stealing small tasks. With a priority-based strategy, a thief selects the victim that has the highest known priority at that time. With a weight-based non-uniformly random strategy, a thief uses the relative weights of victim candidates as their selection probabilities. The proposed selection strategies achieved superior performance compared to uniformly random selection. Our evaluation uses a parallel implementation of the ''highly serial'' version of the Barnes-Hut force calculation algorithm in a shared memory environment and five benchmark programs in a distributed memory environment.

DOI： 10.1109/IA349570.2019.00008

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85078191747&origin=inward

Evaluating Portable Mechanisms for Legitimate Execution Stack Access with a Scheme Interpreter in an Extended SC Language 査読有り

Masahiro Yasugi, Reichi Ikeuchi, Tasuku Hiraishi, Tsuneyasu Komiya

Journal of Information Processing 27 177 - 189 2019年02月

担当区分：責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

© 2019 Information Processing Society of Japan. Scheme implementations should be properly tail-recursive and support garbage collection. To reduce the development costs, a Scheme interpreter called JAKLD, which is written in Java, was designed to use execution stacks simply. JAKLD with interchangeable garbage collectors was reimplemented in C. In addition, we have proposed an efficient C-based implementation written in an extended C language called XC-cube, which features language mechanisms for implementing high-level programming languages such as “L-closures” for legitimate execution stack access, with which a running program/process can legitimately access data deeply in execution stacks (C stacks). L-closures are lightweight lexical closures created from nested function definitions. In addition to enhanced C compilers, we have portable implementations of L-closures, which are translators from an extended S-expression based C language into the standard C language. Furthermore, we have another mechanism for legitimate execution stack access, called “closures”. Closures are standard lexical closures created from nested function definitions. Closures can also be implemented using translators. In this study, JAKLD was reimplemented in an extended SC language (S-expression based C language) that features nested functions to evaluate (L-)closures and their implementations, including translators.

DOI： 10.2197/ipsjjip.27.177

Kyutacar

Scopus

CiNii Article

その他リンク： http://www.jstage.jst.go.jp/browse/ipsjjip/

Probabilistic guards: A mechanism for increasing the granularity of work-stealing programs 査読有り

Hiroshi Yoritaka, Ken Matsui, Masahiro Yasugi, Tasuku Hiraishi, Seiji Umatani

Parallel Computing 82 19 - 36 (Available online 22 June 2018) 2019年02月

担当区分：責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

© 2018 Elsevier B.V. We propose probabilistic guards and analyze their performance. To reduce the total task division cost, probabilistic guards can prevent thief workers from stealing small tasks from victim workers probabilistically. In this study, we have implemented probabilistic guards on a work-stealing framework called Tascell. Without an upper limit to the number of repeated probabilistically prevented steal attempts, a thief may repeat an unbounded number of probabilistically prevented steal attempts until success if a victim uses a probabilistic guard that rejects steal attempts with a non-zero probability. We measured the actual numbers of repeated attempts until success, and evaluated the performance of probabilistic guards with various upper limits. In this paper, we also propose virtual probabilistic guards that act as probabilistic guards without repeating probabilistically prevented steal attempts. Virtual probabilistic guards exhibit superior performance compared to probabilistic guards. Our evaluation is based on parallelized “highly serial” force calculation in a shared memory environment and five Tascell programs in a distributed memory environment.

DOI： 10.1016/j.parco.2018.06.003

Scopus

その他リンク： https://www.sciencedirect.com/journal/parallel-computing

Parallelization of Extracting Connected Subgraphs with Common Itemsets in Distributed Memory Environments 査読有り

Shingo Okuno, Tasuku Hiraishi, Hiroshi Nakashima, Masahiro Yasugi, Jun Sese

Journal of Information Processing 25 ( 0 ) 256 - 267 2017年02月

記述言語：英語掲載種別：研究論文（学術雑誌）

© 2017 Information Processing Society of Japan. This paper proposes a parallel implementation of graph mining that extracts all connected subgraphs with common itemsets, of which the size is not less than a given threshold, from a graph and from itemsets associated with vertices of the graph, in distributed memory environments using the task-parallel language Tascell. With regard to this problem, we have already proposed parallelization of a backtrack search algorithm named COPINE and its implementation in shared memory environments. In this implementation, all workers share a single table, which is controlled by locks, that contains the knowledge acquired during the search to obviate the need for unnecessary searching. This sharing method is not practical in distributed memory environments because it would lead to a drastic increase in the cost of internode communications. Therefore, we implemented a sharing method in which each computing node has a table and sends its updates to the other nodes at regular time intervals. In addition to this, the high task creation cost for COPINE is problematic and thus the conventional work-stealing strategy in Tascell, which aims to minimize the number of internode work-steals, significantly degrades the performance since it increases the number of intran-ode work-steals for small tasks. We solved this problem by promoting workers to enable them to request tasks from external nodes. We also employed a work-stealing strategy based on estimation of the sizes of tasks created by victim workers. This approach enabled us to achieve good speedup performance with up to 8 nodes × 16 workers.

DOI： 10.2197/ipsjjip.25.256

Scopus

CiNii Article

その他リンク： http://www.jstage.jst.go.jp/browse/ipsjjip/

Evaluation of an MPI-Based Implementation of the Tascell Task-Parallel Language on Massively Parallel Systems 査読有り

Daisuke Muraoka, Masahiro Yasugi, Tasuku Hiraishi, Seiji Umatani

Proceedings of the 45th International Conference on Parallel Processing Workshops (ICPPW 2016) (Ninth International Workshop on Parallel Programming Models and Systems Software for High-End Computing P2S2 2016, held in conjunction with ICPP 2016) 161 - 170 2016年08月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Philadelphia 2016年08月16日 - 2016年08月16日

© 2016 IEEE. Tascell is a task parallel language that supports distributed memory environments. The conventional implementation of Tascell realizes inter-node communication with TCP/IP communication via Tascell servers. This implementation is suitable for dynamic addition of computation nodes and wide-area distributed environments. On the other hand, in supercomputer environments, TCP/IP may not be available for inter-node communication and there may be no appropriate places for deploying Tascell servers. In this study, we have developed a server-less implementation of Tascell that realizes inter-node communication with MPI communication in order to evaluate its performance on massively parallel systems. It performs well on four Xeon Phi coprocessors (with 456 workers) and the K computer, for instance, our 19-queens solver achieves a 4615-fold speedup relative to a serial implementation with 7168 workers on the K computer. Our server-less implementation realizes deadlock freedom, although it only requires the two-sided communication paradigm and the MPI-THREAD-FUNNELED support level. On Xeon Phi coprocessors, we compare our implementation with other implementations that employ TCP/IP or the MPI-THREAD-MULTIPLE support level.

DOI： 10.1109/ICPPW.2016.36

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84991010630&origin=inward

Extending a Work-Stealing Framework with Probabilistic Guards 査読有り

Hiroshi Yoritaka, Ken Matsui, Masahiro Yasugi, Tasuku Hiraishi, Seiji Umatani

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Philadelphia 2016年08月16日 - 2016年08月16日

© 2016 IEEE. We propose probabilistic guards and analyze their performance. To reduce the total task division cost, probabilistic guards can prevent thief workers from stealing small tasks from victim workers probabilistically. In this study, we have implemented probabilistic guards on a work-stealing framework called Tascell and have confirmed that they perform well. In theory, a thief may repeat an unbounded number of probabilistically prevented steal attempts until success if a victim uses a probabilistic guard that rejects steal attempts with a non-zero probability. Therefore, in this paper, we also propose a mechanism that invalidates probabilistic guards on demand by setting an upper limit to the number of repeated probabilistically prevented steal attempts. We evaluate its potential effects on probabilistic guards by measuring the actual numbers of repeated attempts until success. We also evaluate the performance of probabilistic guards with various upper limits. Finally, we propose and evaluate virtual probabilistic guards that act as probabilistic guards without repeating probabilistically prevented steal attempts and they exhibit superior performance.

DOI： 10.1109/ICPPW.2016.37

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84991000191&origin=inward

Reducing Redundant Search in Parallel Graph Mining using Exceptions 査読有り

Shingo Okuno, Tasuku Hiraishi, Hiroshi Nakashima, Masahiro Yasugi, Jun Sese

Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW 2016) (21st International Workshop on High-Level Parallel Programming Models and Supportive Environments HIPS 2016, held in conjunction with IPDPS 2016) 328 - 337 2016年05月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Chicago 2016年05月23日 - 2016年05月23日

© 2016 IEEE. This paper proposes an implementation of a parallel graph mining algorithm using a task-parallel language having exception handling features. The performance of a straightforward task-parallel implementation is poor for many practical backtrack search algorithms due to pruning employed in them, a worker may prune a useless subtree, which is pruned before traversal in the sequential search algorithms for search space reduction, after another worker starts the traversal of it resulting in a large amount of redundant search. Such redundancy will be significantly reduced by letting a worker know that the subtree which it is traversing is pruned so that it aborts the traversal. This abortion can be implemented elegantly and efficiently using the task-parallel language that has a mechanism for exception handling by which all running parallel tasks in a try block with an exception are automatically aborted. We applied this abort mechanism to the graph mining algorithm called COPINE, which is practically used for drug discovery, using the task-parallel language Tascell. As a result, we reduced the search space by 31.9% and the execution time by 27.4% in a 28-worker execution.

DOI： 10.1109/IPDPSW.2016.136

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84991687921&origin=inward

An Implementation of Exception Handling with Collateral Task Abortion 査読有り

Tasuku Hiraishi, Shingo Okuno, Masahiro Yasugi

Journal of Information Processing 24 ( 2 ) 2016年03月