研究者詳細 - 八杉　昌宏

論文 - 八杉　昌宏

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

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月

Design and Implementation of a Java Bytecode Manipulation Library for Clojure 査読有り

Seiji Umatani, Tomoharu Ugawa, Masahiro Yasugi

Journal of Information Processing 23 ( 5 ) 716 - 729 2015年09月

Parallelization of Extracting Connected Subgraphs with Common Itemsets 査読有り

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

IPSJ Transactions on Programming 7 ( 3 ) 22 - 39 2014年07月

L-Closureの呼び出しコストの削減査読有り

田附正充, 八杉昌宏, 平石拓, 馬谷誠二

情報処理学会論文誌　プログラミング 6 ( 2 ) 13 - 32 2013年08月

A Proper Performance Evaluation System That Summarizes Code Placement Effects 査読有り

Masahiro Yasugi, Yuki Matsuda, Tomoharu Ugawa

Proceedings of the 11th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE '13) 41 - 48 2013年06月

Safeアンビエントに基づく分散アプリケーション開発用Lisp環境査読有り

林奉行, 馬谷誠二, 八杉昌宏, 湯淺太一

コンピュータソフトウェア 30 ( 1 ) 231 - 256 2013年02月

Automatic and Tunable Multi-Level Locality Improvement with a Lisp Garbage Collector 査読有り

Masahiro Yasugi, Shingo Yuasa, Taiichi Yuasa

Proceedings of the International Lisp Conference 53 - 61 2012年10月

SEAN: Support Tool for Detecting Rule Violations in JNI Coding 査読有り

Haruna Nishiwaki, Tomoharu Ugawa, Seiji Umatani, Masahiro Yasugi, Taiichi Yuasa

IPSJ Transactions on Programming 5 ( 3 ) 23 - 28 2012年08月

日本ソフトウェア科学会第28回大会報告

八杉昌宏

コンピュータソフトウェア ( 日本ソフトウェア科学会 ) 29 ( 1 ) 240 - 250 2012年02月

Parallel Graph Traversals using Work-Stealing Frameworks for Many-core Platforms 査読有り

Masahiro Yasugi, Tasuku Hiraishi, Seiji Umatani, Taiichi Yuasa

Journal of Information Processing 20 ( 1 ) 128 - 139 2012年01月

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

Parallel programming/execution frameworks for many/multi-core platforms should support as many applications as possible. In general, work-stealing frameworks provide efficient load balancing even for irregular parallel applications. Unfortunately, näi{dotless}ve parallel programs which traverse graph-based data structures (e.g., for constructing spanning trees) cause stack overflow or unacceptable load imbalance. In this study, we develop parallel programs to perform probabilistically balanced divide-and-conquer graph traversals. We propose a programming technique for accumulating overflowed calls for the next iteration of repeated parallel stages. In an emerging backtracking-based work-stealing framework called "Tascell," which features on-demand concurrency, we propose a programming technique for long-term exclusive use of workspaces, leading to a similar technique also in the Cilk framework. © 2012 Information Processing Society of Japan.

DOI： 10.2197/ipsjjip.20.128

Scopus

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

バックトラックに基づく動的負荷分散フレームワークTascell

平石拓, 八杉昌宏

京都大学学術情報メディアセンター全国共同利用版広報 ( 京都大学学術情報メディアセンター ) 10 ( 1 ) 31 - 42 2011年06月

Safe AmbientsのためのJavaフレームワーク査読有り

岡田翔太, 馬谷誠二, 林奉行, 八杉昌宏, 湯淺太一

情報処理学会論文誌　プログラミング 4 ( 3 ) 26 - 41 2011年06月

Abstract Machines for Safe Ambients in Wide-Area and Mobile Networks 査読有り

Seiji Umatani, Masahiro Yasugi, Taiichi Yuasa

Proceedings of the 13th International Conference on Coordination Models and Languages (COORDINATION 2011),LNCS 6721 172 - 186 2011年06月

SC言語処理系における変形規則の再利用機構査読有り

平石拓, 八杉昌宏, 湯淺太一

コンピュータソフトウェア 28 ( 1 ) 258 - 271 2011年02月

L-Closureを用いた真に末尾再帰的なSchemeインタプリタ査読有り

八杉昌宏, 平石拓, 小島啓史, 馬谷誠二, 小宮常康, 湯淺太一

情報処理学会論文誌プログラミング 3 ( 5 ) 1 - 17 2010年12月

Dynamic Graph Traversals for Concurrent Rewriting using Work-Stealing Frameworks for Multicore Platforms 査読有り

Masahiro Yasugi, Tasuku Hiraishi, Seiji Umatani, Taiichi Yuasa

Proceedings of the 16th International Conference on Parallel and Distributed Systems (ICPADS 2010) 406 - 414 2010年12月

Managing Continuations for Proper Tail Recursion 査読有り

Masahiro Yasugi, Tsuneyasu Komiya, Tasuku Hiraishi, Seiji Umatani

Proceedings of the 2010 International Lisp Conference (ILC 2010) 65 - 72 2010年10月

Validating Low-Level Instructions for Fixnums using BDDs 査読有り

Shingo Yuasa, Masahiro Yasugi

Proceedings of the 2010 International Lisp Conference (ILC 2010) 11 - 19 2010年10月

L-Closure：安全な計算状態操作機構

八杉昌宏

情報処理 ( 情報処理学会 ) 51 ( 7 ) 885 - 885 2010年07月

動的名前解決による通信先・移動先の柔軟な指定が可能な分散アンビエントシステムの設計査読有り

馬谷誠二, 八杉昌宏, 湯淺太一

コンピュータソフトウェア 27 ( 2 ) 50 - 61 2010年05月

リターンバリア型実時間ごみ集めの抽象モデル検査査読有り

藤川浩光, 馬谷誠二, 八杉昌宏, 湯淺太一

情報処理学会論文誌プログラミング 2 ( 4 ) 13 - 32 2009年08月

Cache-conscious階層的グループ化データ配置法：Cache-oblivious配置法との実験的比較査読有り

八杉昌宏, 後藤裕輔, 馬谷誠二, 湯淺太一

情報処理学会論文誌プログラミング,巻号 2 ( 3 ) 33 - 47 2009年07月

Backtracking-based Load Balancing 査読有り

Tasuku Hiraishi, Masahiro Yasugi, Seiji Umatani, Taiichi Yuasa

Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2009) 55 - 64 2009年02月

タプル空間によるブラウザ間通信を備えたScheme 処理系の開発査読有り

原悠, 鵜川始陽, 湯淺太一, 八杉昌宏

情報処理学会論文誌プログラミング 1 ( 2 ) 85 - 99 2008年09月

Replication-Based Incremental Compaction 査読有り

Tomoharu Ugawa, Masahiro Yasugi, Taiichi Yuasa

11th IEEE International Symposium on Object/component/service-oriented Real-time distributed Computing 516 - 524 2008年05月

マルチスレッド環境における実時間ごみ集めのためのスレッド再開バリア査読有り

鵜川始陽, 花井亮, 八杉昌宏, 湯淺太一

コンピュータソフトウェア 25 ( 2 ) 135 - 150 2008年04月

L-Closure:高性能・高信頼プログラミング言語の実装向け言語機構査読有り

八杉昌宏, 平石拓, 篠原丈成, 湯淺太一

情報処理学会論文誌：プログラミング 49 ( SIG 1(PRO 35) ) 63 - 83 2008年01月

Memory Usage Improvement Using Runtime Alias Detection 査読有り

Ryo Hanai, Tomoharu Ugawa, Masashi Yoneda, Masahiro Yasugi, Taiichi Yuasa

Trends in Functional Programming, Intellect 7 129 - 144 2007年12月

Improving Search Speed on Pointer-Based Large Data Structures Using a Hierarchical Clustering Copying Algorithm 査読有り

Masahiro Yasugi, Taiichi Yuasa

Post-proceedings of the International Workshop on Innovative Architecture for Future generation Processors and Systems 2007 (IWIA 2007) 43 - 52 2007年12月

Experience with SC: Transformation-based Implementation of Various Language Extensions to C 査読有り

Tasuku Hiraishi, Masahiro Yasugi, Taiichi Yuasa

Proceedings of the International Lisp Conference 103 - 113 2007年04月

リージョン変数の動的なエイリアス判定によるメモリ効率向上査読有り

米田匡史, 鵜川始陽, 花井亮, 八杉昌宏, 湯淺太一

情報処理学会論文誌：プログラミング 47 ( SIG 11(PRO 30) ) 38 - 49 2006年07月

A Type System and Compilation Techniques for Concurrent Objects 査読有り

Masahiro Yasugi

Information and Media Technologies 1 ( 1 ) 15 - 32 2006年06月

Efficient and Portable Implementation of Java-style Exception Handling in C 査読有り

Seiji Umatani, Hirokazu Shobayashi, Masahiro Yasugi, Taiichi Yuasa

IPSJ Digital Courier 2 238 - 247 2006年05月

A Transformation-Based Implementation of Lightweight Nested Functions 査読有り

Tasuku Hiraishi, Masahiro Yasugi, Taiichi Yuasa

IPSJ Digital Courier 2 262 - 279 2006年05月

既存Cヘッダファイルの構文の異なる言語での有効利用査読有り

平石拓, 八杉昌宏, 湯淺太一

コンピュータソフトウェア 23 ( 2 ) 225 - 238 2006年04月

Memory Usage Improvement Using Runtime Alias Detection 査読有り

Ryo Hanai, Tomoharu Ugawa, Masashi Yoneda, Masahiro Yasugi, Taiichi Yuasa

Symposium on Trends in Functional Programming 2006 222 - 234 2006年04月

Lightweight Lexical Closures for Legitimate Execution Stack Access 査読有り

Masahiro Yasugi, Tasuku Hiraishi, Taiichi Yuasa

Proceedings of 15th International Conference on Compiler Construction.(CC2006) 170 - 184 2006年03月

Highly Reliable Embedded Software Development Using Advanced Software Technologies 査読有り

Takuya Katayama, Tatsuo Nakajima, Taiichi Yuasa, Tomoji Kishi, Shin Nakajima, Shuichi Oikawa, Masahiro Yasugi, Toshiaki Aoki, Mitsutaka Okazaki, Seiji Umatani

IEICE Transactions on Information and Systems E88-D ( 6 ) 1105 - 1116 2005年06月

Implementing S-Expression Based Extended Languages in Lisp 査読有り

Tasuku Hiraishi, Masahiro Yasugi, Taiichi Yuasa

International Lisp Conference 2005 179 - 188 2005年06月

Real-Time GC in JeRTy VM Using the Return-Barrier Method 査読有り

Hideaki Saiki, Yoshiharu Konaka, Tsuneyasu Komiya, Masahiro Yasugi, Taiichi Yuasa

8th IEEE International Symposium on Object-oriented Real-time distributed Computing (ISORC 2005) 140 - 148 2005年05月

S式ベースC言語における変形規則による言語拡張機構査読有り

平石拓, 李暁ろ, 八杉昌宏, 馬谷誠二, 湯淺太一

情報処理学会論文誌：プログラミング 46 ( SIG 1(PRO 24) ) 40 - 56 2005年01月

入れ子関数を利用する動的負荷分散と高水準記述査読有り

八杉昌宏, 小宮常康, 湯淺太一

情報処理学会論文誌：コンピューティングシステム 45 ( SIG 11(ACS7) ) 368 - 377 2004年10月

オブジェクト指向並列言語OPAのための遅延正規化手法査読有り

馬谷誠二, 八杉昌宏, 小宮常康, 湯淺太一

情報処理学会論文誌：プログラミング 45 ( SIG 5(PRO 21) ) 12 - 25 2004年05月

階層的グループ化に基づくコピー型ごみ集めによる局所性改善査読有り

八杉昌宏, 伊藤智一, 小宮常康, 湯淺太一

情報処理学会論文誌：プログラミング 45 ( SIG 5(PRO 21) ) 36 - 52 2004年05月

継続の生成におけるスタックコピーの遅延査読有り

鵜川始陽, 皆川宜久, 小宮常康, 八杉昌宏, 湯淺太一

情報処理学会論文誌：プログラミング 44 ( SIG 13(PRO 18) ) 72 - 83 2003年10月

Lazy Stack Copying and Stack Copy Sharing for the Efficient Implementation of Continuations 査読有り

Tomoharu Ugawa, Nobuhisa Minagawa, Tsuneyasu Komiya, Masahiro Yasugi, Taiichi Yuasa

The First Asian Symposium on Programming Languages and Systems (APLAS'03),Springer LNCS 2895 410 - 426 2003年10月

Pursuing Laziness for Efficient Implementation of Modern Multithreaded Languages 査読有り

Seiji Umatani, Masahiro Yasugi, Tsuneyasu Komiya, Taiichi Yuasa

The fifth International Symposium on High Performance Computing (ISHPC-V),Springer LNCS 2858 174 - 188 2003年10月

Scheme 処理系におけるC言語拡張コードへのライトバリア自動挿入査読有り

花井亮, 小宮常康, 八杉昌宏, 湯淺太一

情報処理学会論文誌：プログラミング 44 ( SIG 4(PRO 17) ) 17 - 24 2003年03月

適応的オブジェクトのための局面解析手法査読有り

鎌田十三郎, 八杉昌宏

情報処理学会論文誌：プログラミング 44 ( SIG 2(PRO 16) ) 13 - 24 2003年02月

遅延タスク生成の反復計算向け拡張査読有り

馬谷誠二, 八杉昌宏, 小宮常康, 湯淺太一

情報処理学会論文誌 43 ( 4 ) 948 - 957 2002年04月

入れ子関数を利用したマルチスレッドの実現査読有り

田畑悠介, 八杉昌宏, 小宮常康, 湯淺太一

情報処理学会論文誌：プログラミング 43 ( SIG 3(PRO 14) ) 26 - 40 2002年03月

共有メモリ向けプリミティブとそのGCCを使った実現査読有り

八杉昌宏, 高田潤, 田畑悠介, 小宮常康, 湯淺太一

情報処理学会論文誌：プログラミング 43 ( SIG 1(PRO 13) ) 118 - 132 2002年01月

オブジェクト指向並列言語OPAのためのコード生成手法査読有り

八杉昌宏, 馬谷誠二, 鎌田十三郎, 田畑悠介, 伊藤智一, 小宮常康, 湯淺太一

情報処理学会論文誌：プログラミング 42 ( SIG 11(PRO 12) ) 1 - 13 2001年11月

Javaと相互呼び出し可能なScheme処理系「ぶぶ」における継続機能と例外処理機能の実装査読有り

鵜川始陽, 湯淺太一, 小宮常康, 八杉昌宏

情報処理学会論文誌：プログラミング 42 ( SIG 11(PRO 12) ) 25 - 36 2001年11月

Java上のScheme処理系「ぶぶ」における単一のクラスローダを用いたオブジェクトシステムの実装査読有り

窪田貴志, 湯淺太一, 倉林則之, 八杉昌宏, 小宮常康

情報処理学会論文誌：プログラミング 42 ( SIG 7(PRO 11) ) 57 - 69 2001年07月

リターン・バリア査読有り

湯淺太一, 中川雄一郎, 小宮常康, 八杉昌宏

情報処理学会論文誌：プログラミング 41 ( SIG 9(PRO 8) ) 87 - 99 2000年11月

Hierarchically Structured Synchronization and ExceptionHandling in Parallel Languages Using Dynamic Scope 査読有り

Masahiro Yasugi

Parallel and Distributed Computing for Symbolic and Irregular Applications,World Scientific 122 - 148 2000年05月

Adaptive Objects for Concurrent Accesses 査読有り

Masahiro Yasugi, Shigeyuki Eguchi, Kazuo Taki

Object-Oriented Parallel and Distributed Programming,HERMES Science Publications 187 - 206 2000年01月

動的スコープの利用による並列言語の同期・例外処理の階層的構造化査読有り

八杉昌宏

情報処理学会論文誌：プログラミング 40 ( SIG 4(PRO 3) ) 44 - 57 1999年05月

適応的オブジェクトによる排他制御の実行時緩和査読有り

江口重行, 八杉昌宏, 鎌田十三郎, 瀧和男

情報処理学会論文誌 40 ( 5 ) 2084 - 2092 1999年05月

Eliminating Bottlenecks on Parallel Systems Using Adaptive Objects 査読有り

Masahiro Yasugi, Shigeyuki Eguchi, Kazuo Taki

Proc. of International Conference on Parallel Architectures and Compilation Techniques 80 - 87 1998年10月

並列オブジェクト指向言語のためのガーベジコレクタ査読有り

八杉昌宏

情報処理学会論文誌 39 ( 6 ) .1691 - 1699 1998年06月

　前のページ-次のページ　

<八杉 昌宏>

論文 - 八杉 昌宏

<八杉　昌宏>

論文 - 八杉　昌宏