岩崎 英哉

名誉教授・その他関係者名誉教授

学位

  • 工学博士, 東京大学

研究分野

  • 情報通信, ソフトウェア

学歴

  • 1988年03月
    東京大学, 工学系研究科, 情報工学専攻
  • 1985年03月
    東京大学, 工学系研究科, 情報工学専門課程
  • 1983年03月
    東京大学, 工学部, 計数工学科
  • 1975年04月 - 1978年03月
    麻布高等学校

委員歴

  • 2011年10月 - 2023年09月
    連携会員, 日本学術会議
  • 2016年04月01日 - 2018年03月31日
    プログラミング論研究会主査, 日本ソフトウェア科学会, 学協会
  • 2013年04月01日 - 2018年03月31日
    プログラミング・シンポジウム 幹事長, 情報処理学会, 学協会
  • 2017年06月
    理事, 日本ソフトウェア科学会, 学協会
  • 2008年04月 - 2012年03月
    プログラミング研究会運営委員, 情報処理学会, 学協会
  • 2005年04月 - 2012年03月
    プログラミング研究会論文誌編集委員, 情報処理学会, 学協会
  • 2006年04月 - 2008年03月
    プログラミング研究会論文誌編集委員長, 情報処理学会, 学協会
  • 2006年04月 - 2007年03月
    プログラミング研究会主査, 情報処理学会, 学協会
  • 2003年04月 - 2006年03月
    プログラミング研究会幹事, 情報処理学会, 学協会
  • 2000年04月 - 2004年03月
    プログラミング研究会論文誌編集委員, 情報処理学会, 学協会
  • 1997年04月 - 2000年03月
    プログラミング研究会連絡委員, 情報処理学会, 学協会
  • 1993年
    学会誌編集委員, 日本ソフトウェア科学会, 学協会

受賞

  • 受賞日 2018年03月11日
    日本ソフトウェア科学会プログラミング論研究会
    オブジェクトレイアウトを表すメタオブジェクトを含むヒープに対するスレッド化コンパクション
    日本ソフトウェア科学会 第23回プログラミングおよびプログラミング言語ワークショップ (PPL2021) 論文賞, 小野澤 拓;鵜川 始陽;岩崎 英哉
    国内学会・会議・シンポジウム等の賞
  • 受賞日 2018年03月07日
    日本ソフトウェア科学会プログラミング論研究会
    Fregelコンパイラにおける不要な値送受信の削減
    日本ソフトウェア科学会 第20回プログラミングおよびプログラミング言語ワークショップ (PPL2018) 論文賞, 加藤直斗;岩崎英哉
    国内学会・会議・シンポジウム等の賞

論文

  • Haskell Library for Safer Virtual Machine Introspection (Experience Report)
    Takato Otsuka; Hideya Iwasaki
    Proc. ACM SIGPLAN Haskell Symposium 2023 (Haskell 2023), ACM, 掲載ページ 89-96, 出版日 2023年09月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • The TABLET Programming Learning Environment: from Block-based to Text-based Programming
    Takumi Miyajima; Hideya Iwasaki; Yasushi Kuno
    Journal of Information Processing, 30巻, 掲載ページ 729-741, 出版日 2022年10月, 査読付
    研究論文(学術雑誌), 英語
  • Generating Virtual Machine Code of JavaScript Engine for Embedded Systems
    Yuta Hirasawa; Hideya Iwasaki; Tomoharu Ugawa; Hiro Onozawa
    Journal of Information Processing, 30巻, 掲載ページ 679-693, 出版日 2022年10月, 査読付
    研究論文(学術雑誌), 英語
  • Replication-based Object Persistence by Reachability
    Kotaro Matsumoto; Tomoharu Ugawa; Hideya Iwasaki
    Proc. 2022 ACM SIGPLAN International Symposium on Memory Management (ISMM 2022), 掲載ページ 43-56, 出版日 2022年06月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Fregel: a functional domain-specific language for vertex-centric large-scale graph processing
    Hideya Iwasaki; Kento Emoto; Akimasa Morihata; Kiminori Matsuzaki; Zhenjiang Hu
    Journal of Functional Programming, Cambridge University Press (CUP), 32巻, 掲載ページ e4:1-e4:69, 出版日 2022年01月, 査読付, Abstract
    The vertex-centric programming model is now widely used for processing large graphs. User-defined vertex programs are executed in parallel over every vertex of a graph, but the imperative and explicit message-passing style of existing systems makes defining a vertex program unintuitive and difficult. This article presents Fregel, a purely functional domain-specific language for processing large graphs and describes its model, design, and implementation. Fregel is a subset of Haskell, so Haskell tools can be used to test and debug Fregel programs. The vertex-centric computation is abstracted using compositional programming that uses second-order functions on graphs provided by Fregel. A Fregel program can be compiled into imperative programs for use in the Giraph and Pregel+ vertex-centric frameworks. Fregel’s functional nature without side effects enables various transformations and optimizations during the compilation process. Thus, the programmer is freed from the burden of program optimization, which is manually done for existing imperative systems. Experimental results for typical examples demonstrated that the compiled code can be executed with reasonable and promising performance.
    研究論文(学術雑誌)
  • アプリケーションと実行環境に適応したカスタマイズが可能なJavaScript処理系
    小野澤拓; 岩崎英哉; 鵜川始陽
    コンピュータソフトウェア, 38巻, 3号, 掲載ページ 23-40, 出版日 2021年08月, 査読付
    研究論文(学術雑誌), 日本語
  • Fusuma: Double-Ended Threaded Compaction
    Hiro Onozawa; Tomoharu Ugawa; Hideya Iwasaki
    Proc. 2021 ACM SIGPLAN International Symposium on Memory Management (ISMM 2021), 掲載ページ 94-106, 出版日 2021年06月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Region-based Detection of Essential Differences in Image-based Visual Regression Testing
    Haruto Tanno; Yu Adachi; Yu Yoshimura; Katsuyuki Natsukawa; Hideya Iwasaki
    Journal of Information Processing, 情報処理学会, 28巻, 掲載ページ 268-278, 出版日 2020年04月, 査読付
    研究論文(学術雑誌), 英語
  • Collecting type information using unit tests for customizing javascript virtual machines
    Tomoharu Ugawa; Hideya Iwasaki; Takafumi Kataoka
    Proceedings of the 14th Workshop on Implementation, Compilation and Optimization of Object-Oriented Languages, Programs and Systems, ICOOOLPS 2019, Association for Computing Machinery, Inc, 出版日 2019年07月19日, To use JavaScript for Internet of Things (IoT), it is essential to reduce the size of the virtual machine (VM). Although operators in JavaScript are polymorphic, many applications apply operators to only a limited set of datatypes. Thus, customizing a VM to include only implementations of operators of datatypes used can reduce the size of the VM. In this research, we determine the set of operand datatypes that are possibly given to each operator for individual applications. Because JavaScript is a dynamically typed programming language, it is difficult to infer types accurately. Instead, as a practical approach, we obtain type information from executions of unit tests of the application. We implemented a prototype system to record datatypes that are given to each operator in executions of unit tests for Jasmine. The system does not record operands of operators executed by the Jasmine's code but only those by the application's code. We applied this system to two small applications and found that it determined type information with high accuracy.
    研究論文(国際会議プロシーディングス), 英語
  • Fregel コンパイラにおける不要な値送受信の削減
    加藤直斗; 岩崎英哉
    コンピュータソフトウェア, 36巻, 2号, 掲載ページ 28-46, 出版日 2019年05月, 査読付
    研究論文(学術雑誌), 日本語
  • dajFS: A New File System with Per-Directory Adaptive Journaling
    Wataru Aoyama; Hideya Iwasaki
    Journal of Information Processing, 27巻, 掲載ページ 369-377, 出版日 2019年05月, 査読付
    研究論文(学術雑誌), 英語
  • Suspend-less Debugging for Interactive and/or Realtime Programs
    Haruto Tanno; Hideya Iwasaki
    Proc. 12th IEEE International Conference on Software Testing, Verification and Validation (ICST 2019), 掲載ページ 194-205, 出版日 2019年04月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • eJSTK: Building JavaScript Virtual Machines with Customized Datatypes
    Tomoharu Ugawa; Hideya Iwasaki; Takafumi Kataoka
    Journal of Computer Languages, 51巻, 掲載ページ 261-279, 出版日 2019年04月, 査読付
    研究論文(学術雑誌), 英語
  • Optimizing Declarative Parallel Distributed Graph Processing by Using Constraint Solvers
    Akimasa Morihata; Kento Emoto; Kiminori Matsuzaki; Zhenjiang Hu; Hideya Iwasaki
    Proc. 14th International Symposium on Functional and Logic Programming (FLOPS 2018), Lecture Notes in Computer Science 10818, 掲載ページ 166-181, 出版日 2018年05月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • A Framework for Constructing JavaScript Virtual Machines with Customized Datatype Representations
    Takafumi Kataoka; Tomoharu Ugawa; Hideya Iwasaki
    Proc. 33rd ACM/SIGAPP Symposium on Applied Computing (SAC 2018), 掲載ページ 1238-1247, 出版日 2018年04月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • A Debugger-Cooperative Higher-Order Contract System in Python
    Ryoya Arai; Shigeyuki Sato; Hideya Iwasaki
    Proc. 14th Asian Symposium on Programming Languages and Systems (APLAS 2016), Lecture Notes in Computer Science 10017, Springer Verlag, 掲載ページ 148-168, 出版日 2016年11月, 査読付, Contract programming is one of the most promising ways of enhancing the reliability of Python, which becomes increasingly desired. Higher-order contract systems that support fully specifying the behaviors of iterators and functions are desirable for Python but have not been presented yet. Besides, even with them, debugging with contracts in Python would still be burdensome because of delayed contract checking. To resolve this problem, we present PyBlame, a higher-order contract system in Python, and ccdb, a source-level debugger equipped with features dedicated to debugging with delayed contract checking. PyBlame and ccdb are designed on the basis of the standard of Python and thus friendly to many Python programmers. We have experimentally confirmed the advantage and the efficacy of PyBlame and ccdb through the web framework Bottle.
    研究論文(国際会議プロシーディングス), 英語
  • Think Like a Vertex, Behave Like a Function! A Functional DSL for Vertex-Centric Big Graph Processing
    Kento Emoto; Kiminori Matsuzaki; Zhenjiang Hu; Akimasa Morihata; Hideya Iwasaki
    Proc. 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016), ASSOC COMPUTING MACHINERY, 掲載ページ 200-213, 出版日 2016年09月, 査読付, The vertex-centric programming model, known as "think like a vertex", is being used more and more to support various big graph processing methods through iterative super steps that execute in parallel a user-defined vertex program over each vertex of a graph. However, the imperative and message-passing style of existing systems makes defining a vertex program unintuitive. In this paper, we show that one can benefit more from "Thinking like a vertex" by "Behaving like a function" rather than "Acting like a procedure" with full use of side effects and explicit control of message passing, state, and termination. We propose a functional approach to vertex-centric graph processing in which the computation at every vertex is abstracted as a higher-order function and present Fregel, a new domain-specific language. Fregel has clear functional semantics, supports declarative description of vertex computation, and can be automatically translated into Pregel, an emerging imperative-style distributed graph processing framework, and thereby achieve promising performance. Experimental results for several typical examples show the promise of this functional approach.
    研究論文(国際会議プロシーディングス), 英語
  • Improving Floating-Point Numbers: A Lazy Approach to Adaptive Accuracy Refinement for Numerical Computations
    Hideyuki Kawabata; Hideya Iwasaki
    Proc. 25th European Symposium on Programming (ESOP 2016), Lecture Notes in Computer Science 9632, SPRINGER-VERLAG BERLIN, 掲載ページ 390-418, 出版日 2016年04月, 査読付, Numerical computation using floating-point numbers is prone to accuracy degradation due to round-off errors and cancellation of significant digits. Although multiple-precision arithmetic might alleviate this problem, it is difficult to statically decide the optimal degree of precision for each operation in a program. This paper presents a solution to this problem: the partial results in floating-point representations are incrementally improved using adaptive control. This process of adaptive accuracy refinement is implemented using lazy lists, each one containing a sequence of floating-point numbers with gradually improving accuracies. The computation process is driven by the propagation of demand for more accurate results. The concept of this improving floating-point number (IFN) mechanism was experimentally implemented in two ways: as a Haskell library and as a pure C library. Despite the simple approach, the results for numerical problems demonstrated the effectiveness of this mechanism.
    研究論文(国際会議プロシーディングス), 英語
  • Integrating Lua into C for embedding Lua interpreters in a C application
    Akira Tanimura; Hideya Iwasaki
    Proc. 31st ACM/SIGAPP Symposium on Applied Computing (SAC 2016), Association for Computing Machinery, 掲載ページ 1936-1943, 出版日 2016年04月, 査読付, Most scripting languages provide a C API that enables them to cooperate with programs written in C. The scripting language Lua is designed to be embedded in other host languages. However, when embedding Lua interpreters in a C program, the programmer must use complicated C API functions to write glue code between C and Lua. Obeying the protocols of Lua's C API not only increases the development cost but also makes the program error prone. We propose LuCa, a domain specific language for developing integrated applications of Lua and C, with C as the host language. LuCa enables the programmer to write glue code in a combination of Lua and C with some syntactic extensions. By using LuCa, the programmer need not use C API functions
    the programmer can directly write Lua-like code, which is much clearer than C code that uses many API calls. We have implemented a LuCa processor as a translator from LuCa code into C code that calls appropriate C API functions. The translated code can be compiled by a standard C compiler and executed by linking a standard Lua interpreter.
    研究論文(国際会議プロシーディングス), 英語
  • Efficient Use of Hardware Transactional Memory for Parallel Mesh Generation
    Tetsu Kobayashi; Shigeyuki Sato; Hideya Iwasaki
    Proc. 44th International Conference on Parallel Processing (ICPP 2015), IEEE, 掲載ページ 600-609, 出版日 2015年09月, 査読付, Efficient transactional executions are desirable for parallel implementations of algorithms with graph refinements. Hardware transactional memory (HTM) is promising for easy yet efficient transactional executions. Long HTM transactions, however, abort with high probability because of hardware limitations. Unfortunately, Delaunay mesh refinement (DMR), which is an algorithm with graph refinements for mesh generation, causes long transactions. Its parallel implementation naively based on HTM therefore leads to poor performance. To utilize HTM efficiently for parallel implementation of DMR, we present an approach to shortening transactions. Our HTM-based implementations of DMR achieved significantly higher throughput and better scalability than a naive HTM-based one and lock-based ones. On a quad-core Haswell processor, the absolute speedup of one of our implementations was up to 2.64 with 16 threads.
    研究論文(国際会議プロシーディングス), 英語
  • Thunk Recycling for Lazy Functional Languages: Operational Semantics and Correctness
    Yasunao Takano; Hideya Iwasaki
    Proc. 30th ACM/SIGAPP Symposium on Applied Computing (SAC 2015), ASSOC COMPUTING MACHINERY, 掲載ページ 2079-2086, 出版日 2015年04月, 査読付, Lazy evaluation helps programmers write clear programs. However, it has significant run-time overheads for building many as-yet unevaluated expressions, or thunks. Because thunk allocation is a space-consuming task, it is important to reduce the number of thunks in order to improve the performance of a lazy functional program. To resolve this problem, a mechanism named thunk recycling have been proposed. Thunk recycling suppresses thunk generation by reusing and updating an already allocated thunk at the tail of a list, on the condition that the thunk is singly referred. The preliminary implementation of thunk recycling has been developed in Glasgow Haskell Compiler and has succeeded in reducing total memory allocations for benchmark programs. This paper addresses the formal issue of thunk recycling. We present a small-step operational semantics of the thunk recycling and show the correctness of this mechanism on the basis of bisimulation.
    研究論文(国際会議プロシーディングス), 英語
  • Design and implementation of thunk recycling in the Glasgow Haskell Compiler
    Yasunao Takano; Hideya Iwasaki; Shigeyuki Sato
    Computer Software, Japan Society for Software Science and Technology, 32巻, 1号, 掲載ページ 253-287, 出版日 2015年, The lazy functional programming language Haskell has attracted much attention in recent years. The Glasgow Haskell Compiler (GHC) is a state-of-the-art and de facto standard compiler and runtime system for Haskell. Much of the literature on Haskell has been devoted to GHC and many new mechanism have been introduced into GHC. However, since the implementation of the current GHC is huge and complicated, it is hard to introduce a new mechanism into GHC. In such a situation, our prior work on thunks, which are internal objects to enable lazy evaluation, also incorporated our thunk recycling into GHC and succeeded in reducing memory allocations. The method transforms a program into the program that enables thunk recycling by reusing and updating an already-allocated thunk. Although the essence of thunk recycling has already been published in our paper, it does not cover our overall implementation in GHC, a large and complicated software. In this paper, we present the entire sophisticated implementation of thunk recycling in GHC, explaining various design decisions and implementation techniques and report experimental results of our techniques. Furthermore, we have improved our implementation by using additional techniques based on our knowledge of GHC. As a result, we have reduced the overhead of our method successfully. The knowledge of the implementation obtained from our experience which used GHC for the base of a programming language research is also described. In particular, the fact that GHC is written by Haskell contributes to the extendibility of its implementation.
    研究論文(学術雑誌), 日本語
  • Glasgow Haskell Compiler 上の遅延オブジェクト再利用手法の設計と実装
    高野保真; 岩崎英哉; 佐藤重幸
    コンピュータソフトウェア, 32巻, 1号, 掲載ページ 253-287, 出版日 2015年01月, 査読付
    研究論文(学術雑誌), 日本語
  • LibDSL: A Library for Developing Embedded Domain Specific Languages in D via Template Metaprogramming
    Masato Shioda; Hideya Iwasaki; Shigeyuki Sato
    Proc. 13th International Conference on Generative Programming: Concepts and Experiences (GPCE 2014), ASSOC COMPUTING MACHINERY, 掲載ページ 63-72, 出版日 2014年09月, 査読付, This paper presents a library called LibDSL that helps the implementer of an embedded domain specific language (EDSL) effectively develop it in D language. The LibDSL library accepts as input some kinds of "specifications" of the EDSL that the implementer is going to develop and a D program within which an EDSL source program written by the user is embedded. It produces the front-end code of an LALR parser for the EDSL program and back-end code of the execution engine. LibDSL is able to produce two kinds of execution engines, namely compiler-based and interpreter-based engines, either of which the user can properly choose depending on whether an EDSL program is known at compile time or not. We have implemented the LibDSL system by using template metaprogramming and other advanced facilities such as compile-time function execution of D language. EDSL programs developed by means of LibDSL have a nice integrativeness with the host language.
    研究論文(国際会議プロシーディングス), 英語
  • XQuery Streaming by Forest Transducers
    Shizuya Hakuta; Sebastian Maneth; Keisuke Nakano; Hideya Iwasaki
    Proc. 30th IEEE International Conference on Data Engineering (ICDE 2014), IEEE, 掲載ページ 952-963, 出版日 2014年04月, 査読付, Streaming of XML transformations is a challenging task and only a few existing systems support streaming. Research approaches generally define custom fragments of XQuery and XPath that are amenable to streaming, and then design custom algorithms for each fragment. These languages have several shortcomings. Here we take a more principled approach to the problem of streaming XQuery-based transformations. We start with an elegant transducer model for which many static analysis problems are well-understood: the Macro Forest Transducer (MFT). We show that a large fragment of XQuery can be translated into MFTs - indeed, a fragment of XQuery, that can express important features that are missing from other XQuery stream engines, such as GCX: our fragment of XQuery supports XPath predicates and let-statements. We then use an existing streaming engine for MFTs and apply a well-founded set of optimizations from functional programming such as strictness analysis and deforestation. Our prototype achieves time and memory efficiency comparable to the fastest known engine for XQuery streaming, GCX. This is surprising because our engine relies on the OCaml built in garbage collector and does not use any specialized buffer management, while GCX's efficiency is due to clever and explicit buffer management.
    研究論文(国際会議プロシーディングス), 英語
  • Adaptive Scanning Reduces Sweep Time for the Lisp2 Mark-Compact Garbage Collector
    Kazuya Morikawa; Tomoharu Ugawa; Hideya Iwasaki
    Proc. 2013 International Symposium on Memory Management (ISMM 2013), ASSOC COMPUTING MACHINERY, 掲載ページ 15-26, 出版日 2013年06月, 査読付, Mark-compact garbage collection helps long-running programs avoid fragmentation. The Lisp2 mark-compact collector is a classic but still widely-used compaction algorithm. It sequentially scans the entire heap to compact all live objects at one end of the heap while preserving their order of addresses. Since the heap is generally large, this scanning takes a long time. Although some collectors adopt a separate bitmap into which mark bits of objects are stored to reduce the scanning time, we observed that scanning the bitmap can take longer than scanning the heap if objects are densely located. We propose a new scanning method from this observation, which adaptively alternates methods of scanning depending on heap usage; it scans those parts of the heap where live objects are densely located whereas it scans the bitmap for the remaining parts. We implemented this scanning method in the Lisp2 collector of Jikes RVM. The experimental results revealed that the adaptive scanner scanned faster than the method that only scanned the heap and the method that only scanned the bitmap.
    研究論文(国際会議プロシーディングス), 英語
  • Pruning with Improving Sequences in Lazy Functional Programs
    Hideya Iwasaki; Takeshi Morimoto; Yasunao Takano
    Higher-Order and Symbolic Computation, 24巻, 4号, 掲載ページ 281-309, 出版日 2012年08月, 査読付, This paper presents a library based on improving sequences and demonstrates that they are effective for pruning unnecessary computations while retaining program clarity. An improving sequence is a monotonic sequence of approximation values of a final value that are improved gradually according to some ordering relation. A computation using improving sequences proceeds by demanding for the next approximation value. If an approximation value in the middle of the improving sequence has sufficient information to yield the result of some part of the program, the computations that produce the remaining values can be pruned. By combining suitable improving sequences and primitive functions defined for the sequences, we can write efficient programs in the same form as simple and naive programs. We give examples that show the effectiveness of improving sequences and show by program calculation that a simple minimax-like program using improving sequences implements a well-known branch-and-bound searching algorithm. © Springer Science+Business Media, LLC 2012.
    研究論文(学術雑誌), 英語
  • Improvements of Recovery from Marking Stack Overflow in Mark Sweep Garbage Collection
    Tomoharu Ugawa; Hideya Iwasaki; Taiichi Yuasa
    情報処理学会論文誌 プログラミング, 5巻, 1号, 掲載ページ 1-8, 出版日 2012年03月, 査読付, Mark sweep garbage collection (GC) is usually implemented using a mark stack for a depth first search that marks all objects reachable from the root set. However, the required size of the mark stack depends on the application, and its upper bound is proportional to the size of the heap. It is not acceptable in most systems to reserve memory for such a large mark stack. To avoid unacceptable memory overhead, some systems limit the size of the mark stack. If the mark stack overflows, the system scans the entire heap to find objects that could not be pushed due to overflow and traverses their children. Since the scanning takes a long time, this technique is inefficient for applications that are likely to cause overflows. In this research, we propose a technique to record rough locations of objects that failed to be pushed so that they can be found without scanning the entire heap. We use a technique similar to the card table of mostly concurrent GC to record rough locations. © 2012 Information Processing Society of Japan.
    研究論文(学術雑誌), 英語
  • Glasgow Haskell Compiler における再帰的データ構造のための遅延オブジェクトの再利用
    高野保真; 岩崎英哉; 鵜川始陽
    情報処理学会論文誌 プログラミング, 情報処理学会, 5巻, 2号, 掲載ページ 67-78, 出版日 2012年03月, 査読付, 遅延評価は,プログラムの簡潔な記述を可能にするため,純関数型言語などで採用されている.特にリストなどの再帰的データ構造を扱う際には,必要に応じて評価を進めることが可能となり,遅延評価により得られる記述性の向上は大きい.一方,計算を遅延するために必要なオブジェクト(遅延オブジェクト)の生成は,プログラム実行時のオーバヘッドとなってしまうため,効率の良い遅延評価機構を実装するには,遅延オブジェクトの削減が必要である.本論文は,リストのような線形に再帰的に定義される代数データ構造に注目し,必要となる遅延オブジェクトを再利用する手法を提案する.提案手法は,すでに割り当てられている遅延オブジェクトの保持している値を更新して再利用する.このような再利用を可能とするために,提案手法は,コンパイル時にプログラム変換を行い,再利用対象とする遅延オブジェクトへの参照を単一にする.提案手法を,純関数型言語Haskellの処理系であるGlasgow Haskell Compiler上に実装し,実験を行った.その結果,オーバヘッドはあるものの,総メモリ割当て量を削減できることが分かった.Lazy evaluation helps programmers write clear programs. However, it has significant run-time overheads for building many as-yet unevaluated expressions, or thunks. Because thunk allocation is a space-consuming task, it is important to reduce the number of thunks in order to improve the performance of a lazy functional program. We propose static analysis algorithms that achieve the thunk reuse technique. Thunk generation is suppressed by reusing an already allocated thunk at the tail of a list, on the condition that the thunk is singly referred, i.e., pointed to only from the tail field of a cons cell. This method guarantees that reused thunks definitely satisfy this singly referred condition on the basis of a static analysis with program transformations. We have implemented our method in the Glasgow Haskell Compiler and measured total memory allocations and execution times for some programs.
    研究論文(学術雑誌), 日本語
  • SAW: Java Synchronization Selection from Lock or Software Transactional Memory
    Yuji Yamada; Hideya Iwasaki; Tomoharu Ugawa
    Proc. 17th IEEE International Conference on Parallel and Distributed Systems (ICPADS 2011), IEEE, 掲載ページ 104-111, 出版日 2011年12月, 査読付, To rewrite a sequential program into a concurrent one, the programmer has to enforce atomic execution of a sequence of accesses to shared memory to avoid unexpected inconsistency. There are two means of enforcing this atomicity: one is the use of lock-based synchronization and the other is the use of software transactional memory (STM). However, it is difficult to predict which one is more suitable for an application than the other without trying both mechanisms because their performance heavily depends on the application. We have developed a system named SAW that decouples the synchronization mechanism from the application logic of a Java program and enables the programmer to statically select a suitable synchronization mechanism from a lock or an STM. We introduce annotations to specify critical sections and shared objects. In accordance with the annotated source program and the programmer's choice of a synchronization mechanism, SAW generates aspects representing the synchronization processing. By comparing the rewriting cost using SAW and that using individual synchronization mechanism directly, we show that SAW relieves the programmer's burden. Through several benchmarks, we demonstrate that SAW is an effective way of switching synchronization mechanisms according to the characteristics of each application.
    研究論文(国際会議プロシーディングス), 英語
  • Automatic Parallelization via Matrix Multiplication
    Shigeyuki Sato; Hideya Iwasaki
    Proc. 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2011), ASSOC COMPUTING MACHINERY, 掲載ページ 470-479, 出版日 2011年06月, 査読付, Existing work that deals with parallelization of complicated reductions and scans focuses only on formalism and hardly dealt with implementation. To bridge the gap between formalism and implementation, we have integrated parallelization via matrix multiplication into compiler construction. Our framework can deal with complicated loops that existing techniques in compilers cannot parallelize. Moreover, we have sophisticated our framework by developing two sets of techniques. One enhances its capability for parallelization by extracting max-operators automatically, and the other improves the performance of parallelized programs by eliminating redundancy. We have also implemented our framework and techniques as a parallelizer in a compiler. Experiments on examples that existing compilers cannot parallelize have demonstrated the scalability of programs parallelized by our implementation.
    研究論文(国際会議プロシーディングス), 英語
  • Starvation-free Heap Size for Replication-Based Incremental Compacting Garbage Collection
    Tomoharu Ugawa; Hideya Iwasaki; Taiichi Yuasa
    Proc. International Lisp Conference (ILC 2010), 掲載ページ 43-50, 出版日 2010年10月, 査読付, We present a method to estimate the amount of the heap required to execute application programs on runtime systems with our replication-based incremental compacting garbage collector. Our method provides a strategy for adjusting the timing to trigger garbage collection and choosing a heap region to be evacuated during partial compaction, which moves all objects in one part of the heap to the rest of the heap. The method is also used to determine the minimum heap size that guarantees free memory never exhausts during incremental garbage collection. Furthermore, we ensure that allocation never fails due to fragmentation with the strategy. The strategy is to reserve a contiguous free area and to prohibit the allocator from allocating in that area until garbage collection is triggered. When it becomes necessary to use the reserved free area to satisfy an allocation request, we trigger garbage collection. We show that, with this strategy, an application never fails to allocate objects with a larger heap than R + 2√2Ra + 3a plus space overhead caused by the heap layout, where R is the maximum amount of live objects and a is the upper bound of the possible amount of allocation during a single collection cycle. © 2010 ACM.
    研究論文(国際会議プロシーディングス), 英語
  • サーバ/クライアント自動分割を備えたWebフレームワークの設計と実装
    稲津和磨; 岩崎英哉
    情報処理学会論文誌 プログラミング, 情報処理学会, 3巻, 4号, 掲載ページ 1-15, 出版日 2010年09月, 査読付, 近年Google Mapsなどに代表される,Ajaxと呼ばれる手法を用いたWebアプリケーションが増加している.Ajaxを用いたWebアプリケーションはサーバ側とクライアント側で動作する2つのプログラムにより構成され,それらが協調して動作する.そのため,煩雑な通信処理を記述する必要があり,さらには,それぞれの実装言語が多くの場合は異なっているため,プログラミングが非常に煩雑になる.そこで本論文では,開発効率の向上を目的として,JavaScriptに基づくプログラム言語でWebアプリケーションを1つのプログラムとして記述し,処理の柔軟な分割を可能とするフレームワークを提案する.また,そのプログラム言語で記述されたプログラムを読み込み,サーバ側で動作するソースコードとクライアント側で動作するソースコードを出力するような機構を設計し,実装した.提案機構は,与えられたプログラムを解析し各構文要素がサーバとクライアントのどちらで実行するべきかを決定する.その際,分割方針を指定することで,同じソースコードから異なる分割を得ることができる.同じ動作をするWebアプリケーションを,提案機構と既存の手法のそれぞれを用いて記述し,プログラムを比較して記述性が向上していることを確認した.また,提案機構によるオーバヘッドは,Webアプリケーションで行われる一般的な処理については問題ない程度の小さなものであることを確認した.Ajax based web applications such as Google Maps have increased in recent years. An Ajax application is composed of the server side program and the client side program. Usually these programs are written in different programming languages. Furthermore, communications between the server and the client have to be explicitly described. For this reason, development of web applications is a very complicated task. To solve this problem, we proposes a framework that enables the user to write a web application as a single program. We have implemented a system that partition such a program into both the server side program and the client side one. It decides which parts of a source program should be executed at the client side or at the server side based on a policy given by the user. We confirmed that our framework makes the development of web applications easier, by comparing a program using our framework with a program using an existing method for the same application. Although our framework causes overhead in execution time, it is acceptable for general web applications.
    研究論文(学術雑誌), 日本語
  • ブラウザで動作するウェブアプリケーションのソースコード隠蔽機構
    折戸隆洋; 岩崎英哉
    情報処理学会論文誌 プログラミング, 3巻, 4号, 掲載ページ 16-26, 出版日 2010年09月, 査読付
    研究論文(学術雑誌), 日本語
  • Improved Replication-Based Incremental Garbage Collection for Embedded Systems
    Tomoharu Ugawa; Hideya Iwasaki; Taiichi Yuasa
    Proc. 2010 International Symposium on Memory Management (ISMM 2010), 掲載ページ 73-82, 出版日 2010年06月, 査読付, We have developed an incremental compacting garbage collector for embedded Java systems. The collector divides the heap into equal sized pages and uses the segregated free lists for fast allocation. Collectors that have such a heap layout have a problem of fragmentation in allocating objects larger than the page size. We solve this problem by using the replication-based incremental compaction. The compactor evacuates all objects in one area, the evacuation area, of the heap, thereby creating a large chunk of free space. We developed an algorithm for choosing the evacuation area that effectively cures fragmentation. The compactor does not use any read-barriers. Instead, it uses a technique similar to the replication-based incremental copying collection. This needs forwarding pointers for all evacuated objects. Rather than introducing an extra field for each object, we use a hash table to store forwarding pointers. Evaluation of this garbage collector implemented in Sun's J2ME Java Virtual Machine showed that all the benchmarks used were able to run without memory starvation using the heap sizes of only 151%-286% of the maximum amount of live data plus 8 KB of the hash table. Experiments on a desktop computer, though it is not a platform for embedded systems, showed that the maximum pause time was shorter than 200 μs, which was comparable to that of our implementation of the snapshot-at-the-beginning collector without compaction. On an ARM processor, the runtime overhead was 1%-16% with 8.0% on average compared to the mark-sweep collector. © 2010 ACM.
    研究論文(国際会議プロシーディングス), 英語
  • A Skeletal Parallel Framework with Fusion Optimizer for GPGPU Programming
    Shigeyuki Sato; Hideya Iwasaki
    Proc. 7th Asian Symposium on Programming Languages and Systems (APLAS 2009), Lecture Notes in Computer Science 5904, SPRINGER-VERLAG BERLIN, 掲載ページ 79-94, 出版日 2009年12月, 査読付, Although today's graphics processing units (GPUs) have high performance and general-purpose computing on GPUs (GPGPU) is actively studied, developing GPGPU applications remains difficult for two reasons. First, both parallelization and optimization of GPGPU applications is necessary to achieve high performance. Second, the suitability of the target application for GPGPU must be determined, because whether at application performs well with GPGPU heavily depends on its inherent properties, which are not obvious from the source code. To overcome these difficulties, we developed a skeletal parallel programming framework for rapid GPGPU application developments. It enables program tin to easily write GPGPU applications and rapidly test them because it generates programs for both GPUs and CPUs from the same source code. It also provides an optimization mechanism based on fusion transformation. Its effectiveness was confirmed experimentally.
    研究論文(国際会議プロシーディングス), 英語
  • A Parallel Skeleton Library for Multi-core Clusters
    Yuki Karasawa; Hideya Iwasaki
    Proc. 38th International Conference on Parallel Processing (ICPP 2009), 掲載ページ 84-91, 出版日 2009年09月, 査読付, A parallel skeleton library is a collection of parallel computations that abstract generic and recurring patterns within parallel programs and conceal parallel behaviors as skeletons. It enables users to develop parallel programs as if they were sequential ones by composing suitable skeletons. However, many existing parallel skeleton libraries for distributed environments do not take into account the potential performance of multicore CPUs, because they operate under the premise that each node (computer) has a single-core CPU. To resolve this problem, this paper proposes the design and implementation of a parallel skeleton library for multi-core clusters. The proposed library adopts a two-stage dynamic task scheduling strategy
    the first is among nodes and the second is among cores. This scheduling strategy enables the library to appropriately balance the load both between nodes and cores. The library also dynamically fuses successive skeleton calls to reduce the cost of control flows and increase the locality of data. The proposed skeletons are implemented from scratch for matrices within a parallel skeleton library called SkeTo by using the template techniques in C++ language. We confirmed that our implementation was efficient through various benchmarks. © 2009 IEEE.
    研究論文(国際会議プロシーディングス), 英語
  • Parallel Skeletons for Variable-Length Lists in SkeTo Skeleton Library
    Haruto Tanno; Hideya Iwasaki
    Proc. 15th International Euro-Par Conference (Euro-Par 2009), Lecture Notes in Computer Science 5704, SPRINGER-VERLAG BERLIN, 掲載ページ 666-677, 出版日 2009年08月, 査読付, Skeletal parallel programming is a promising solution to simplify parallel programming. The approach involves providing genetic and recurring data structures like lists and parallel computation patterns as skeletons that conceal parallel behaviors. However, when we focus on lists, which are usually implemented as one-dimensional arrays, their length is restricted and fixed in existing data parallel skeleton libraries. Due to this restriction, many problems cannot be coded using parallel skeletons. To resolve this problem, this paper proposes parallel skeletons for lists of variable lengths and their implementation within a parallel skeleton library called SkeTo. The proposed skeletons enable us to solve a wide range of problems including those of twin primes, Knight's tour, and Mandelbrot set calculations with SkeTo. We tested and confirmed the efficiency of our implementation of variable-length lists through various experiments.
    研究論文(国際会議プロシーディングス), 英語
  • Haskellプログラムの開発を支援するGHCiデバッガフロントエンド
    根岸純一; 岩崎英哉
    情報処理学会論文誌 プログラミング, 2巻, 3号, 掲載ページ 48-56, 出版日 2009年07月, 査読付
    研究論文(学術雑誌), 日本語
  • Kenro: A Virtual Machine Monitor Mostly Described in Haskell
    Yoshihiro Oyama; Yoshiki Kaneko; Hideya Iwasaki
    Proc. 2009 ACM Symposium on Applied Computing (SAC 2009), 掲載ページ 1940-1941, 出版日 2009年03月, 査読付, We report on our experiences developing a tiny virtual machine monitor, named Kenro, mostly in Haskell as a concrete example of low-level, hardware-dependent system software. The development of Kenro was greatly helped by features of Haskell, including higher-order functions, strong static typing, and the automatic memory management. We describe the advantages and limitations of Haskell studied through our development experience. Copyright 2009 ACM.
    研究論文(国際会議プロシーディングス), 英語
  • Tuning Mechanisms for Two Major Parameters of Apache Web Servers
    Akiyoshi Sugiki; Kenji Kono; Hideya Iwasaki
    Software - Practice and Experience, WILEY-BLACKWELL, 38巻, 12号, 掲載ページ 1215-1240, 出版日 2008年10月, 査読付, Apache web servers are widely used as stand-alone servers or front-ends in multi-tiered web servers. Despite the wide availability of software, it is quite difficult for many administrators to properly configure their web servers. In particular, setting the performance-related parameters is an error-prone and time-consuming task because their values heavily depend on the server environment. In this paper, two mechanisms are described for automatically tuning two performance-related parameters of Apache web servers: KeepAliveTimeout and MaxClients. These mechanisms are easy to deploy because no modifications to the server or the operating system are required. Moreover, they are parameter specific. Although interference between KeepAliveTimeout and MaxClients is inevitable, the tuning mechanisms minimize the correlation by using almost completely independent metrics. Experimental results show that these mechanisms work well for two different workloads; the parameter values are close to optimal and can adapt to workload changes. Copyright (C) 2007 John Wiley & Sons, Ltd.
    研究論文(学術雑誌), 英語
  • 純関数型言語の処理系における効率的な枝刈り機構の実装
    田村和博; 高野保真; 岩崎英哉
    情報処理学会論文誌 プログラミング, 情報処理学会, 1巻, 2号, 掲載ページ 28-41, 出版日 2008年09月, 査読付, 実行効率の良い探索プログラムを書くためには,結果に寄与しない計算を除去する枝刈りが有効であるが,一般に,簡潔なプログラム構造を保ったまま枝刈りの記述をすることは難しい.この問題点を解決するために,Improving Sequence(IS)というデータ構造を用いる手法が提案され,有効性が確認されている.ISとは,ある全的に定義された推移的な二項関係に従い,要求駆動によって単調に最終結果へ近づいていく近似値の列のことである.ISを用いたプログラムでは,枝刈りをするか否かの判断に近似値を用いることができる.従来の純関数型言語上のISの実装はライブラリによるものだったので,近似値の数に比例したヒープ領域を必要とし,効率があまり良くないという問題点があった.この問題点を解決するため,本論文では,ISの近似値が持つ単調性に着目し,また,近似値が枝刈りの判断にのみ用いられ,中間データとしての役割しか持たないことを前提として,純関数型言語において,定数領域しかヒープを消費しないISの実装を提案する.提案手法の効果を確認するため,Glasgow Haskell Compilerに実装を施し,ナップサック問題など,いくつかのプログラムで実験を行った.その結果,問題によってばらつきはあるものの,メモリ消費量において3%~75%程度の減少が見られ,安定的に改善できることが確認できた.また,メモリ消費量を削減することで,多くの場合に実行時間を改善できることも確認できた.Pruning unnecessary computations increases the efficiency of search programs. However, in general, it is hard to write a program that performs pruning while retaining program clarity. A mechanism called Improving Sequence (IS for short) helps the programmers write clear program for pruning computations. An IS is a sequence of approximations that are gradually improved based on a binary relation and approach the final value. Each approximation value can be used to decide whether further computations beyond the approximation can be pruned or not. Existing implementation of an IS on a purely functional language is library-based one, thus much heap space that is proportional to the number of approximations is consumed. To solve this problem, this paper proposes an efficient implementation of an IS that consumes only the constant space within the heap space. The proposed implementation is based on the observation that the approximations with an IS is monotonic and each approximation is used only in the judgment of pruning. We implemented the proposed idea in the Glasgow Haskell Compiler, and made some experiments by running some search programs that use ISes. The results show that the amount of memory consumption is reduced by 3-75%, depending on the program, and the execution time is also reduced in many cases.
    研究論文(学術雑誌), 日本語
  • Parallel Skeletons for Sparse Matrices in SkeTo Skeleton Library
    Yuki Karasawa; Hideya Iwasaki
    情報処理学会論文誌:プログラミング, 49巻, SIG 3 (PRO 36)号, 掲載ページ 1-15, 出版日 2008年03月, 査読付
    研究論文(学術雑誌), 英語
  • A Sandbox with Dynamic Policy Based on Execution Contexts of Applications
    Tomohiro Shioya; Yoshihiro Oyama; Hideya Iwasaki
    Proc. 12th Asian Computing Science Conference (ASIAN 2007), Lecture Notes in Computer Science 4846, SPRINGER-VERLAG BERLIN, 掲載ページ 297-311, 出版日 2007年12月, 査読付, We propose a sandbox system that dynamically changes its behavior according to the application's execution context. Our system allows users to give different policies, each of which specifies permitted system calls, depending on the user functions in which the target application is executing. The target application can be given less privilege than would be possible with other single-policy sandbox systems. We implemented the sandbox by using LKM (Loadable Kernel Module) of Linux that intercepts the system call issued by the application process. We experimentally demonstrated the effectiveness of the sandbox.
    研究論文(国際会議プロシーディングス), 英語
  • 非同期処理のための JavaScript マルチスレッドフレームワーク
    牧大介; 岩崎英哉
    情報処理学会論文誌:プログラミング, 48巻, SIG 12 (PRO 34)号, 掲載ページ 1-18, 出版日 2007年08月, 査読付
    研究論文(学術雑誌), 日本語
  • リクエスト待機間隔を考慮したウェブサーバの keep-alive 時間の自動設定
    杉木彰義; 河野健二; 岩崎英哉
    コンピュータソフトウェア, Japan Society for Software Science and Technology, 24巻, 2号, 掲載ページ 68-78, 出版日 2007年04月, 査読付, インターネットサーバの手動による性能パラメータ調整は,多くの経験や時間を必要とし,管理コストの増大を招くことが知られている.ウェブサーバの主要な性能パラメータであるkeep-alive時間は,適切に設定しない場合,サーバのスループットや応答性を低下させることがある.本論文では,ウェブサーバのkeep-alive時間の自動設定機構を提案する.本機構は管理者の介入を必要とせず,手動設定で求めた値に近いkeep-alive時間に自動設定する.本機構はリクエスト待機間隔を監視しながら,データを送受信していない接続を切断し,データを頻繁に送受信している多くのクライアントからの接続を保つようにkeep-alive時間を設定する.本機構をApacheウェブサーバを対象としたライブラリとして実装し,実験を行った.その結果,異なる2つの負荷に対して,それぞれkeep-alive時間を自動的に設定し,サーバの性能を適切に維持することを確認した.Manual parameter-tuning of Internet servers causes high administrative costs because it requires administrator's expertise and huge amounts of time. The keep-alive parameter, which is one of major parameters in web servers, may cause severe degradation if it is not set properly. In this paper, we present an automatic tuning technique of the keep-alive parameter. Our mechanism adjusts the parameter without administrator's intervention so as to maintain active connections between clients and a server while closing inactive connections by observing request-waiting intervals. We implemented a prototype for Apache web server. Experimental results show that our prototype automatically adjusted the parameter and successfully yielded the nearly optimal server performance on two different workloads.
    研究論文(学術雑誌), 日本語
  • アプリケーション層プロトコルの記述に基づく拡張性に優れたプロトコル処理コード生成系
    阿部勝幸; 岩崎英哉; 河野健二
    コンピュータソフトウェア, 24巻, 2号, 掲載ページ 150-163, 出版日 2007年04月, 査読付
    研究論文(学術雑誌), 日本語
  • Instantly Turning a Naive Exhaustive Search into Three Efficient Searches with Pruning
    Takeshi Morimoto; Yasunao Takano; Hideya Iwasaki
    Proc. 9th International Symposium on Practical Aspects of Declarative Languages (PADL 2007), Lecture Notes in Computer Science 4354, SPRINGER-VERLAG BERLIN, 掲載ページ 65-79, 出版日 2007年01月, 査読付, A technique is described that enables purely functional programmers to write efficient search programs in the same form as simple and naive but; exhaustive search programs. It performs pruning while retaining a simple program form by exploiting a lazy data structure, an improving sequence, which is a monotonical sequence of approximation values that approach the final value. If some approximation value in an improving sequence has sufficient information to yield the result of some part of the program, the computations that produce the values remaining after the approximation can be pruned. On the basis of an exhaustive search program, which can be regarded as the specification of a problem, three important search algorithms, namely best-first, depth-first branch-and-bound, and iterative-deepening, can be obtained by using suitable functions defined on improving sequences. Two specific examples, the eight puzzle problem and the knapsack problem in Haskell, demonstrate that the technique is practical.
    研究論文(国際会議プロシーディングス), 英語
  • 要求駆動計算における要求粒度調節機構
    森本武資; 岩崎英哉
    情報処理学会論文誌, 47巻, 12号, 掲載ページ 3277-3286, 出版日 2006年12月, 査読付
    研究論文(学術雑誌), 日本語
  • A Library of Constructive Skeletons for Sequential Style of Parallel Programming
    Kiminori Matsuzaki; Kento Emoto; Hideya Iwasaki; Zhenjiang Hu
    Proc. First International Conference on Scalable Information Systems (InfoScale 2006), 掲載ページ CDROM, 出版日 2006年05月, 査読付, With the increasing popularity of parallel programming environments such as PC clusters, more and more sequential programmers, with little knowledge about parallel architectures and parallel programming, are hoping to write parallel programs. Numerous attempts have been made to develop high-level parallel programming libraries that use abstraction to hide low-level concerns and reduce difficulties in parallel programming. Among them, libraries of parallel skeletons have emerged as a promising way towards this direction. Unfortunatefy, these libraries are not well accepted by sequential programmers, because of incomplete elimination of lower-level details, ad-hoc selection of library functions, unsatisfactory performance, or lack of convincing application examples. This paper addresses principle of designing skeleton libraries of parallel programming and reports implementation details and practical applications of a skeleton library SkeTo. The SkeTo library is unique in its feature that it has a solid theoretical foundation based on the theory of Constructive Algorithmes, and is practical to be used to describe various parallel computations in a sequential manner. © 2006 ACM.
    研究論文(国際会議プロシーディングス), 英語
  • A Practical Approach to Automatic Parameter-Tuning of Web Servers
    Akiyoshi Sugiki; Kenji Kono; Hideya Iwasaki
    Proc. 10th Asian Computing Science Conference (ASIAN 2005), Lecture Notes in Computer Science 3818, SPRINGER-VERLAG BERLIN, 掲載ページ 146-159, 出版日 2005年12月, 査読付, This paper presents a practical approach to automatically tuning the parameters of the Apache Web server. In particular, two significant parameters, KeepAliveTimeout and MaxClients, are dealt with. The notable features of our approach are twofold. First, it is easy to deploy because no modifications to Apache or the underlying operating system are required. Second, our approach is based on the detailed analysis on how each parameter affects the server's behavior. Experimental results demonstrate that our prototype works well on different workloads; it can discover almost optimal values and quickly adapt to workload changes.
    研究論文(学術雑誌), 英語
  • 最適化機構を持つC++並列スケルトンライブラリ
    明石良樹; 松崎公紀; 岩崎英哉; 筧一彦; 胡振江
    コンピュータソフトウェア, 22巻, 3号, 掲載ページ 214-221, 出版日 2005年07月, 査読付
    研究論文(学術雑誌), 日本語
  • 需要変化に動的に対応する伸縮自在サーバ群の基本機構
    揚妻匡邦; 河野健二; 岩崎英哉; 益田隆司
    電子情報通信学会論文誌 D-I, 一般社団法人電子情報通信学会, J88-D-1巻, 4号, 掲載ページ 767-779, 出版日 2005年04月, 査読付, インターネット上では様々なサービスが展開されており, 社会的な基盤としてその役割はますます重要になっている.インターネット上のサービスへの需要が増加すると, サービスを提供するサーバの負荷が高まり, サービスの遅延や最悪の場合サービスの一時停止などといったサービスの質の低下へとつながる.サービスの質の低下を抑える方法として, 一般に同じサービスを提供することができる計算機を複数台用意し, サービスへの需要を各計算機へと分散する手法が用いられている.しかし, インターネット上のサービスへの需要は常に変動しているため, あらかじめ需要を予測して計算機資源を設置することは難しい.そこで本論文では, サービスへの需要の増減に応じ, サービスを提供する計算機資源の総量を自動的に調節する基盤を提案する.本基盤により構成されるサーバ群を伸縮自在サーバ群と呼ぶ.伸縮自在サーバ群では, 複数の計算機が動いており, 互いにPeer-to-Peer方式を用いて通信し, サービスを提供する計算機の増減を行う.本論文では, 伸縮自在サーバ群と, 伸縮自在サーバ群上でサービスを提供する計算機を増減させるための基本機構を提案し, その有効性をシミュレーションを用いて検証する.
    研究論文(学術雑誌), 日本語
  • A New Parallel Skeleton for General Accumulative Computations
    Hideya Iwasaki; Zhenjiang Hu
    International Journal of Parallel Programming, SPRINGER/PLENUM PUBLISHERS, 32巻, 5号, 掲載ページ 389-414, 出版日 2004年10月, 査読付, Skeletal parallel programming enables programmers to build a parallel program from ready-made components (parallel primitives) for which efficient implementations are known to exist, making both the parallel program development and the parallelization process easier. Constructing efficient parallel programs is often difficult, however, due to difficulties in selecting a proper combination of parallel primitives and in implementing this combination Without having unnecessary creations and exchanges of data among parallel primitives and processors. To overcome these difficulties, we propose a powerful and general parallel skeleton, accumulate, which can be used to naturally code efficient Solutions to problems as well as be efficiently implemented in parallel using Message Passing Interface (MPI).
    研究論文(学術雑誌), 英語
  • A Fusion-Embedded Skeleton Library
    Kiminori Matsuzaki; Kazuhiko Kakehi; Hideya Iwasaki; Zhenjiang Hu; Yoshiki Akashi
    Proc. 10th International Euro-Par Conference (Euro-Par 2004), Lecture Notes in Computer Science 3149, SPRINGER-VERLAG BERLIN, 掲載ページ 644-653, 出版日 2004年08月, 査読付, This paper addresses a new framework for designing and implementing skeleton libraries, in which each skeleton should not only be efficiently implemented as is usually done, but also be equipped with a structured interface to combine it efficiently with other skeletons. We illustrate our idea with a new skeleton library for parallel programming in C++. It is simple and efficient to use just like other C++ libraries. A distinctive feature of the library is its modularity: Our optimization framework treats newly defined skeletons equally to existing ones if the interface is given. Our current experiments are encouraging, indicating that this approach is promising both theoretically and in practice.
    研究論文(学術雑誌), 英語
  • ファイル移送に基づく分散ファイルシステムの設計と実装
    村田光一; 河野健二; 岩崎英哉; 益田隆司
    コンピュータソフトウェア, 21巻, 4号, 掲載ページ 43-48, 出版日 2004年06月, 査読付
    研究論文(学術雑誌), 日本語
  • 枝刈り機構とメモ化機構をもつ言語
    森本武資; 岩崎英哉; 竹内郁雄
    コンピュータソフトウェア, 21巻, 4号, 掲載ページ 55-60, 出版日 2004年06月, 査読付
    研究論文(学術雑誌), 日本語
  • An Interactive Proofreading System for Inappropriately Selected Words on Using Predictive Text Entry
    Hideya Iwasaki; Kumiko Tanaka-Ishii
    Proc. 1st International Joint Conference on Natural Language Processing (IJCNLP 2004), Lecture Notes in Artificial Intelligence 3248, SPRINGER-VERLAG BERLIN, 掲載ページ 755-764, 出版日 2004年03月, 査読付, Predictive text entry systems on computers like kana-to-kanji conversion provide a mechanism that enables users to select among possible words for a given input. Mistakes in selection are relatively common, and they introduce real-word errors. A proofreading system is thus needed to detect and correct real-word errors on a computer without imposing troublesome operations on users. To this end, a practical proofreading system for Japanese text is proposed. The system automatically detects possible real-word homonym errors, and for each detected word, suggests substitution candidates of the same pronunciation. The user can either choose the most appropriate one or leave the original untouched. The system uses an algorithm based on the Naive Bayesian method. Although the proofreading system was implemented for homonym errors in Japanese text, its design concept and algorithm are also applicable to other languages. The client program of the proofreading system is implemented on the Emacs text editor and works in real time.
    研究論文(学術雑誌), 英語
  • Self-configurable Mirror Servers for Automatic Adaptation to Service Demand Fluctuation
    Masakuni Agetsuma; Kenji Kono; Hideya Iwasaki
    Proc. 8th Asian Computing Science Conference (ASIAN 2003), Lecture Notes in Computer Science 2896, SPRINGER-VERLAG BERLIN, 掲載ページ 18-32, 出版日 2003年12月, 査読付, Various network services are becoming more and more important serving roles in the social infrastructure in the Internet. The more clients a service has, the more load the server has, which obviously lowers the quality of service. To balance load and maintain quality, multiple servers (mirror servers) are commonly provided that are able to provide access to the same service. However, it is difficult to estimate the required number of mirror servers in advance. To overcome this, we propose a new concept called self-configurable server groups and discuss its basic mechanism where all server nodes communicate with one another in a peer-to-peer style to adjust to the expected number of servers. We also demonstrate the effectiveness of the proposed mechanism via some simulations.
    研究論文(学術雑誌), 英語
  • モバイルコード技術によるアプリケーション層プロトコルのユーザ透過な配布機構
    揚妻匡邦; 河野健二; 岩崎英哉; 益田隆司
    電子情報通信学会論文誌 D-I, 一般社団法人電子情報通信学会, J86-D-1巻, 6号, 掲載ページ 389-401, 出版日 2003年06月, 査読付
    研究論文(学術雑誌), 日本語
  • Developing a Lisp-based Preprocessor for TEX Documents
    Hideya Iwasaki
    Software - Practice and Experience, JOHN WILEY & SONS LTD, 32巻, 14号, 掲載ページ 1345-1363, 出版日 2002年11月, 査読付, TEX allows users to define a macro that abstracts a sequence of typesetting commands. However, defining macros is not easy for most users, because the mechanism of macro expansion in TEX is complicated. As a remedy for this situation, a new system that enables users to define macros for TEX documents as Lisp programs has been developed. The system acts as a preprocessor for TEX; given a document that contains Lisp programs as S-expressions, the system expands each S-expression on the basis of Lisp's evaluation rules, thus generating an ordinary TEX document. The system is very flexible and easy-to-use, thanks to the underlying language's general-purpose data structure, i.e. the S-expression. applicative order evaluation, and rich set of predefined functions. This paper also demonstrates that the proposed system is really, effective for practical use by giving some concrete examples of Lisp macros, some of which are difficult to define in terms of TEX commands. The system is currently implemented on the Emacs Lisp, and a user-friendly environment is thus available in the Emacs text editor. Copyright (C) 2002 John Wiley Sons, Ltd.
    研究論文(学術雑誌), 英語
  • Characterizing Feasible Pattern Sets with Minimum Number of Breaks
    Ryuhei Miyashiro; Hideya Iwasaki; Tomomi Matsui
    Proc. 4th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2002), Lecture Notes in Computer Science 2740, 掲載ページ 78-99, 出版日 2002年08月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • An Accumulative Parallel Skeleton for All
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    Proc. 2002 European Symposium on Programming (ESOP 2002), Lecture Notes in Computer Science 2305, SPRINGER-VERLAG BERLIN, 掲載ページ 83-97, 出版日 2002年04月, 査読付, Parallel skeletons intend to encourage programmers to build a parallel program from ready-made components for which efficient implementations are known to exist, making the parallelization process simpler. However, it is neither easy to develop efficient parallel programs using skeletons nor to use skeletons to manipulate irregular data, and moreover there lacks a systematic way to optimize skeletal parallel programs. To remedy this situation, we propose a novel parallel skeleton, called accumulate, which not only efficiently describes data dependency in computation but also exhibits nice algebraic properties for manipulation. We show that this skeleton significantly eases skeletal parallel programming in practice, efficiently manipulating both regular and irregular data, and systematically optimizing skeletal parallel programs.
    研究論文(学術雑誌), 英語
  • Flattening Transformation for Efficient Segmented Computation - Segmented Diffusion Theorem.
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    The Third Asian Workshop on Programming Languages and Systems, APLAS'02, Shanghai Jiao Tong University, Shanghai, China, November 29 - December 1, 2002, Proceedings, 掲載ページ 246-257, 出版日 2002年, 査読付
  • Efficient Parallel Skeletons for Nested Data Structures
    Tomonari Takahashi; Hideya Iwasaki; Zhenjiang Hu
    Proc. 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2001), C S R E A PRESS, 掲載ページ 728-734, 出版日 2001年06月, 査読付, Skeleton programming enables programmers to build parallel programs easier by providing efficient ready-made skeletons. In addition to primitive skeletons, diffusion skeleton has been proposed for rather complicated problems, abstracting a good combination of primitive skeletons. However, since they equally treat each element in target data the existing skeletons are not always efficient for nested data structure where sizes of inner elements may be remarkably different. To resolve this problem, this paper proposes a new parallel skeleton, segmented diffusion, specially for nested data structure. The proposed skeleton is a nested version of the diffusion skeleton and similarly provides a proper combination of primitive nested skeletons. This paper also describes implementation of the skeleton and some experimental results, showing that the proposed skeleton is efficient and can be applied to a wider class of problems.
    研究論文(国際会議プロシーディングス), 英語
  • Diffusion after Fusion - Deriving Efficient Parallel Algorithms
    Raku Shirasawa; Zhenjiang Hu; Hideya Iwasaki
    Proc. 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2001), C S R E A PRESS, 掲載ページ 735-741, 出版日 2001年06月, 査読付, Parallel skeletons are ready-made components whose efficient implementations are known to exist. Using them programmers can develop parallel programs without concerning about lower level of implementation. However, programmers may often suffer from the difficulty to choose a proper combination of parallel skeletons so as to construct efficient parallel programs. In this paper. we propose a new method, namely diffusion after fusion, which can not only guide a programmer to develop efficient parallel programs in a systematic way, but also be suitable for optimization of skeleton parallel programs. In this method, first we remove unnecessary intermediate data structure by fusion without being conscious of parallelism. Then we parallelize the fused program by diffusion. Using the Line-of-sight problem, this paper shows that the proposed method is quite effective.
    研究論文(国際会議プロシーディングス), 英語
  • 漸次的組化と融合による関数プログラムの最適化
    岩崎英哉; 胡振江; 武市正人
    コンピュータソフトウェア, 18巻, 0号, 掲載ページ 46-59, 出版日 2001年01月, 査読付
    研究論文(学術雑誌), 日本語
  • Context-Sensitive Detection and Correction of Homonym Errors in Japanese Texts
    Hideya Iwasaki; Kumiko Tanaka-Ishii; Kei Tateno; Masato Takeichi
    Proc. 5th International Workshop on Information Retrieval with Asian Languages (IRAL 2000), Association for Computing Machinery, Inc, 掲載ページ 215-216, 出版日 2000年09月, 査読付, In Japanese and Chinese, the use of kanji characters has produced words with many homonyms. Thus, the correct 'spelling' (kanji) for a word can depend on its context. Computer text entry systems provide a mechanism for users to choose between possible spellings, but mistakes are relatively common. We propose a new context-sensitive algorithm to correct this kind of spelling error. The algorithm detects errors in input text and suggests alternative spellings to the user. Our experimental results have shown maximally about 98~ of accuracy rate.
    研究論文(国際会議プロシーディングス), 英語
  • Diff: A Powerful Parallel Skeleton
    Seiji Adachi; Hideya Iwasaki; Zhenjiang Hu
    Proc. 2000 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2000), C S R E A PRESS, 掲載ページ 2175-2181, 出版日 2000年06月, 査読付, Skeleton parallel programming encourages programmers to build a parallel program from ready-made components for which efficient implementations are known to exist, making both the parallel program development and the parallelization process easier. However, programmers often suffer from the difficulty to choose a proper combination of parallel primitives so as to construct efficient parallel programs. To overcome this difficulty, we propose a new powerful parallel skeleton diff derived from the diffusion theorem, showing how it can be used to naturally code efficient solutions to problems, and how it can be efficiently implemented in parallel using MPI (Message Passing Interface).
    研究論文(国際会議プロシーディングス), 英語
  • プログラム融合変換の実用的有効性の検証
    尾上能之; 胡振江; 岩崎英哉; 武市正人
    コンピュータソフトウェア, 17巻, 3号, 掲載ページ 81-85, 出版日 2000年05月, 査読付
    研究論文(学術雑誌), 日本語
  • 初心者入門用言語「若葉」の言語仕様と処理系の実装
    吉良智樹; 並木美太郎; 岩崎英哉
    情報処理学会論文誌:プログラミング, 40巻, SIG10(PRO5)号, 掲載ページ 28-38, 出版日 1999年12月, 査読付
    研究論文(学術雑誌), 日本語
  • Calculating Accumulations
    Zhenjiang Hu; Hideya Iwasaki
    New Generation Computing, SPRINGER, 17巻, 2号, 掲載ページ 153-173, 出版日 1999年06月, 査読付, The accumulation strategy consists of generalizing a function over an algebraic data structure by inclusion of an extra parameter, an accumulating parameter, for reusing and propagating intermediate results. However, there remain two major difficulties in this accumulation strategy. One is to determine where and when to generalize the original function. The other, surprisingly not yet receiving its worthy consideration, is how to manipulate accumulations. To overcome these difficulties, we propose to formulate accumulations as higher order catamorphisms, and provide several general transformation rules for calculating accumulations (i.e., finding and manipulating accumulations) by calculation-based (rather than a search-based) program transformation methods. Some examples are given for illustration.
    研究論文(学術雑誌), 英語
  • Diffusion: Calculating Efficient Parallel Programs
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    Proc. 1999 ACM SIGPLAN International Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM 1999), 掲載ページ 85-94, 出版日 1999年01月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • 第三言語を介した対訳辞書の作成
    田中(石井)久美子; 梅村恭司; 岩崎英哉
    情報処理学会論文誌, 一般社団法人情報処理学会, 39巻, 6号, 掲載ページ 1915-1924, 出版日 1998年06月, 査読付, 第三言語を介して対訳辞書を自動作成するアルゴリズムを論じ,現存の対訳辞書との比較により抽出結果を検討する.和英辞典と英仏辞典から英語(第三言語)を仲介として和仏辞典を作成する際には,英語において機械的に辞書を合体させるだけでは第三言語の語の多義性により不適当な訳語が生じる.したがって,正しい訳語のみを自動抽出する手法が必要となる.本研究では,訳語関係のグラフ,語の形態素が持つ表意を利用した手法を提案する.実際に既存の中辞典規模の電子辞書を用いて名詞,動詞,形容詞に対して実験を行い,既存の辞書にはない訳語が得られるという有効性を示した.When putting two dictionaries,such as Japanese-English and English-French,together into a bilingual dictionary,the Japanese-French dictionary,it is necessary to discriminate equivalencies from inappropriate words caused by the ambiguity in the third language(which is English in the example).We propose a method to treat this by exploiting the structures of dictionaries to measure the similarity of the meanings of words.The resulting dictionary is a word-to-word bilingual dictionary of nouns,verbs,adjectives,and can be used to refine the entries and equivalencies in published bilingual dictionaries.
    研究論文(学術雑誌), 日本語
  • Towards Manipulation of Mutually Recursive Functions
    Hideya Iwasaki; Zhenjiang Hu; Masato Takeichi
    Proc. 3rd Fuji International Symposium on Functional and Logic Programming (FLOPS 1998), 掲載ページ 61-79, 出版日 1998年04月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • 関係代数による UNITY ループの意味づけ
    徐良為; 武市正人; 岩崎英哉
    情報処理学会論文誌, 39巻, 3号, 掲載ページ 646-655, 出版日 1998年03月, 査読付
    研究論文(学術雑誌), 日本語
  • 蓄積引数を持つ関数プログラムの融合変換
    岩崎英哉; 胡振江
    情報処理学会論文誌, 一般社団法人情報処理学会, 39巻, 3号, 掲載ページ 664-673, 出版日 1998年03月, 査読付, 関数プログラムでは,関数合成間で受け渡される中間的データ構造を生成しないように,関数合成を1つの関数に融合する(融合変換する)ことが,効率改善にとって重要である.構成的アルゴリズム論は,Catamorphism Hylomorphismなどと呼ばれる特定の再帰パターンと,これらに対する強力な変換定理を用いて,上の問題の解決を試みる.本論文は,蓄積引数を持つ関数の融合変換のための2つの手法?高階関数のCatamorphismに基づく方法とHylomorphismに基づく方法?に注目し,前者に基づく融合変換操作は,後者による融合変換に帰着できることを示す.まず簡単な具体例を通して両手法の変換手順を示した後,一般の場合について上の主張を証明する.本論文で示される事実により,構成的アルゴリズム論に基づくプログラム変換システムでは,Hylomorphismを用いた変換だけを考えればよいという,有益な結論が得られる.In order to gain the efficiency of functional programs,it is important to fuse the composition and eliminate intermediate data structures passed through the composition.Constructive Algorithmics is one of the promising approaches to this problem.This paper focuses on functions with accumulative parameters,and discusses two transformation strategies-one based on higher-order catamorphisms and the other based on hylomorphisms.It is shown that programs which can be transformed by the former can be also transformed by the latter.The result of this paper shows that program transformation system based on Constructive Algorithmics has only to take into account the strategy by hylomorphisms.
    研究論文(学術雑誌), 日本語
  • Relational Semantics for Locally Nondeterministic Programs
    Liangwei Xu; Masato Takeichi; Hideya Iwasaki
    New Generation Computing, SPRINGER VERLAG, 15巻, 3号, 掲載ページ 339-361, 出版日 1997年09月, 査読付, Introducing nondeterministic operators in a conventional deterministic language gives rise to various semantic difficulties. One of the problems is that there has been no semantic domain that is wholly satisfactory for denoting nondeterministic programs.
    In this paper, we propose an approach based on relational algebra. We divide the semantics of a nondeterministic program into two parts. The first part concerns the angelic aspect of programs and the second part concerns the demonic aspect of programs. Because each semantic function used in these parts is monotonic with respect to an ordering on relations, the existence of the fixed points of recursively defined nondeterministic programs is ensured.
    研究論文(学術雑誌), 英語
  • Clustering Co-occurrence Graph based on Transitivity
    Kumiko Tanaka-Ishii; Hideya Iwasaki
    Proc. 5th Workshop on Very Large Corpora (WVLC 1997), 掲載ページ 91-100, 出版日 1997年08月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Tupling Calculation Eliminates Multiple Data Traversals
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi; Akihiko Takano
    Proc. 1997 ACM SIGPLAN International Conference on Functional Programming (ICFP 1997), ACM Press, 掲載ページ 164-175, 出版日 1997年06月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Formal Derivation of Efficient Parallel Programs by Construction of List Homomorphisms
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    ACM Transactions on Programming Languages and Systems, ASSOC COMPUTING MACHINERY, 19巻, 3号, 掲載ページ 444-461, 出版日 1997年05月, 査読付, It has been attracting much attention to make use of list homomorphisms in parallel programming because they ideally suit the divide-and-conquer parallel paradigm, However, they have been usually treated rather informally and ad hoc in the development of efficient parallel programs. What is worse is that some interesting functions, e.g., the maximum segment sum problem, are basically not list homomorphisms. In this article, we propose a systematic and formal way for the construction of a list homomorphism for a given problem so that an efficient parallel program is derived. We show, with several well-known but nontrivial problems, how a straightforward, and ''obviously'' correct, but quite inefficient solution to the problem can be successfully turned into a semantically equivalent ''almost list homomorphism.'' The derivation is based on two transformations, namely tupling and fusion, which are defined according to the specific recursive structures of list homomorphisms.
    研究論文(学術雑誌), 英語
  • A Calculational Fusion System HYLO
    Yoshiyuki Onoue; Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    Proc. IFIP TC2 Working Conference on Algorithmic Languages and Calculi, CHAPMAN & HALL, 掲載ページ 76-106, 出版日 1997年02月, 査読付, Fusion, one or the most useful transformation tactics for deriving efficient programs, is the process whereby separate pieces of programs are fused into a single one, leading to an efficient program without intermediate data structures produced. In this paper, we report our on-going investigation on the design and implementation of an automatic transformation system HYLO which performs fusion transformation in a more systematic and more general way than any other systems. The distinguished point of our system is its calculational feature based on simple application of transformation laws rather than traditional search-based transformations.
    研究論文(国際会議プロシーディングス), 英語
  • An Extension of the Acid Rain Theorem
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    Proc. 2nd Fuji International Workshop on Functional and Logic Programming (FLOPS 1996), 掲載ページ 91-105, 出版日 1996年11月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Construction of List Homomorphisms by Tupling and Fusion
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    Proc. Mathematical Foundations of Computer Science (MFCS 1996), Lecture Notes in Computer Science 1113, 掲載ページ 407-418, 出版日 1996年09月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Extraction of Lexical Translations from Non-Aligned Corpora
    Kumiko Tanaka; Hideya Iwasaki
    Proc. 16th International Conference on Computer Linguistics (COLING 1996), 掲載ページ 580-585, 出版日 1996年08月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Formal Derivation of Parallel Program for 2-Dimensional Maximum Segment Sum Problem
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    Proc. Annual European Conference on Parallel Processing (EuroPar 1996), Lecture Notes in Computer Science 1123, 掲載ページ 553-562, 出版日 1996年08月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Deriving Structural Hylomorphisms from Recursive Definitions
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    Proc. 1996 ACM SIGPLAN International Conference on Functional Programming (ICFP 1996), 掲載ページ 73-82, 出版日 1996年05月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Cheap tupling in calculational form
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 1140巻, 掲載ページ 471-472, 出版日 1996年, 査読付, In functional programming, a program prog is usually expressed as compositions of transformations over data structures while each transformation is defined by a recursion Ri traversing over its input data structure, namely prog = R1 o… oRn.
    研究論文(国際会議プロシーディングス), 英語
  • 部品合成による漢字スケルトンフォントの作成
    田中哲朗; 岩崎英哉; 長橋賢児; 和田英一
    情報処理学会論文誌, 一般社団法人情報処理学会, 36巻, 9号, 掲載ページ 2122-2131, 出版日 1995年09月, 査読付, 多くの漢字は偏や旁などの基本的な部品の組合せからできている。本論文では、このことを利用して、漢字を具体的な座標を含まない抽象的な組合せ情報で定義しておき、プログラムによって部品を組み合わせてフォントを生成する方法を提案する。各部品は組合せによって大きさが変化するので、通常は様々な大きさの部品を用意しないと組み合わせて使うことができない。しかし、線の太さを自由に変えることのできるスケルトンフォントを使えば、あるサイズでデザインした部品をサイズを変更して使うことができる。そこで、本研究では論文(1)で提案した複数書体に対応可能なスケルトンフォントの形式で部品のデザインを表現する。組合せの種類として、横方向、縦方向、片方の部品の空白部分に他方の部品を配置する嵌込みが考えられる。JIS X0208に含まれるすべての漢字をこの3種類の組合せで表現して、最初の2つの組合せを扱うだけでもある程度デザインコストを減らせるが、嵌込みを扱うと更に効果があることを確かめた。また、未知の漢字が現われた時に、既知の部品の組合せだけで表現できる可能性を、JIS X0212の漢字の何割がJIS X0208の漢字の部品で表現できるかによって見積もった。表現した漢字を表示、印刷するためには組合せアルゴリズムが重要である。そこで、一番容易な横方向の組合せを実現するために単純な方法をいくつか実装し、評価をおこなった。その中でもっとも良かった組合せアルゴリズムをもとに縦方向、嵌込みのプログラムを実装し、JIS X0208とJIS X0212のフォントセットを作成した。これが単純なアルゴリズムで作成されたものにもかかわらず、ある程度の品質に達していることを確かめた。
    研究論文(学術雑誌), 日本語
  • Promotional Transformation of Monadic Programs
    Zhenjiang Hu; Hideya Iwasaki
    Proc. Fuji International Workshop on Functional and Logic Programming (FLOPS 1995), 掲載ページ 196-210, 出版日 1995年07月, 査読付
    研究論文(国際会議プロシーディングス), 英語
  • Derivation of Algorithms by Introduction of Generation Functions
    Liangwei Xu; Hideya Iwasaki; Masato Takeichi
    New Generation Computing, SPRINGER VERLAG, 13巻, 1号, 掲載ページ 75-98, 出版日 1994年12月, 査読付, A specification is a mathematical description of the intent we want a program to behave, while an algorithm is a formal description of a program that satisfies the specification. When we want to write an algorithm by defining data domians and functions over these domains, it is common to use recursion equations for function definitions. However, recursion equations lack imaginability such as existential quantifiers in predicate calculus. In this paper we show how executable algorithms are derived from specifications written in ordinary set-theoretic formulas, and illustrate it by deriving several kinds of sorting algorithms as well as a graph algorithm.
    研究論文(学術雑誌), 英語
  • オブジェクトの形状が定義可能な並列記号処理言語用核の設計と実現
    岩崎英哉; 竹内幹雄
    情報処理学会論文誌, 一般社団法人情報処理学会, 34巻, 8号, 掲載ページ 1752-1761, 出版日 1993年08月, 査読付, 本論文では、並列記号処理言語の処理系を実装する際の墓礎となる"核"の設計・実現法について述ぺ、実際にトランスビュータのために開発したシステムTK800について議論する。TK800核は、利用者プログラムに対して、非同期スレッド間通信、スレッドの動的生成などの高レベルの機能を提供するが、中でも特に重要なのは、記号処理言語の処理系記述を念頭においた、ごみ集めを含むヒープ管理である。TK800核は、オブジェクトヘのポインタの形、いくつかの種類のオブジェクト本体の形状を既定義のものとして与え、さらに、利用者 プログラム独自のオブジェクトを定義・利用する方法も提供する。それは多 くの場合は、マクロを機械的に定義するだけですむ。ヒープ領域のごみ集めは、核が責任 をもって行うので、利用者は、オブジェクトの割り当て、形状、ごみ集めなどのヒープ管理こ煩わされることなく、言語処理系を構成することが可能である。本論文では、TK800の内部構成、並列関数型言語の解釈実行系のTK800を利用した記述についても述べ、さらに設計・実現法についての考察も加える。
    研究論文(学術雑誌), 日本語
  • マルチプロセッサ Unix マシン上における並列言語処理系の実装法の検討
    岩崎英哉
    情報処理学会論文誌, 一般社団法人情報処理学会, 33巻, 11号, 掲載ページ 1351-1360, 出版日 1992年11月, 査読付, 本論文では 並列処理言語の処理系をUnix系共有メモリ型マルチプロセッサ計算機上に実装する際に直面するいくつかの問題点について議論する.ここでは マルチューザの下でCPU資源を使う環境を想定する・さらに 並列処理言語の実際例を示し 考察も加える 実現例を示すのは 並列性言語仕様として持つLisp方言mutilispである.従来のUnixでは システムコールの重さ・機能そのものや機能面の細かさ 並列性記述のためのライブラリが単一プロセッサ向きである点などが マルチプロセッサにおける処理系作成上の問題点となる.mutilispではインタプリタ本体で効率的に解決するのが困難な問題については これをインタプリタ上で動いているLispプログラムに通知する機構を導入し そのプログラムに処置を委ねる という解決法をとる.その結果 問題解決のためには 上位部の特定のプログラム間の関係のみに注目すればよくなり たとえばCPUの放棄も容易に実現でき 処理系の柔軟性が向上することになる。また 本論文では 処理系の性能についても簡単にふれ mutilispでのアプローチが有効であることを示した.本論文で提案する手法は 実行時の動的スケジューリングをおこなうシステムで有効であり 多くの言語処理系に対して応用が可能である.
    研究論文(学術雑誌), 日本語
  • mUtilisp: a Lisp Dialect for Parallel Processing
    Hideya Iwasaki
    Proc. US Japan Workshop on Parallel Lisp, Lecture Notes in Computer Science 441, SPRINGER, 掲載ページ 316-321, 出版日 1990年06月, 査読付
    研究論文(学術雑誌), 英語
  • Lispにおける並列動作の記述と実現
    岩崎英哉
    情報処理学会論文誌, 28巻, 5号, 掲載ページ 465-470, 出版日 1987年05月, 査読付
    研究論文(学術雑誌), 日本語

MISC

  • 頂点主体並列グラフ処理の制約解消器による効率化
    森畑 明昌; 江本 健斗; 松崎 公紀; 胡 振江; 岩崎 英哉
    日本ソフトウェア科学会, 出版日 2017年09月18日, 日本ソフトウェア科学会大会論文集, 34巻, 掲載ページ 415-429, 日本語, 0913-5391, 40021462421
  • 複数の頂点主体グラフ計算フレームワーク向けの中間表現とコード生成器
    松崎 公紀; 岩崎 英哉; 江本 健斗; 胡 振江; 森畑 明昌
    日本ソフトウェア科学会, 出版日 2017年09月18日, 日本ソフトウェア科学会大会論文集, 34巻, 掲載ページ 493-502, 日本語, 0913-5391, 40021462571
  • Rubyに対するGradual typingの導入に向けて
    丹治将貴; 中野圭介; 岩崎英哉
    出版日 2017年01月, 第58回プログラミング・シンポジウム予稿集
  • 大規模グラフ並列処理のための関数型領域特化言語Fregelとその評価
    江本 健斗; 松崎 公紀; 胡 振江; 森畑 明昌; 岩崎 英哉
    日本ソフトウェア科学会, 出版日 2016年09月07日, 日本ソフトウェア科学会大会論文集, 33巻, 掲載ページ 227-242, 日本語, 0913-5391, 40021053340
  • グラフ問題を効率的に解くためのハードウェアトランザクショナルメモリの利用
    小林 哲; 佐藤 重幸; 岩崎 英哉
    近年,ハードウェアトランザクショナルメモリ(HTM)を搭載したCPUが市場にリリースされてきている.HTMのような投機的並列実行は,グラフアルゴリズムの並列処理に有効であることが知られている.そのため,HTMをグラフ問題の並列処理に利用することは有用と考えられる.しかし,現実的なグラフ問題の並列処理におけるトランザクションは,グラフの探索と更新をアトミックに行う必要があるため長くなりやすい.HTMではハードウェアの制限によって,このようなトランザクションを効率的に実行することは難しい.この問題を解決するため,本発表では,HTMのトランザクションを短縮する方法を提案する.提案方法では,計算処理とグラフの探索部分をトランザクションの外に出し,グラフの更新だけをトランザクション内で実行する.本発表では,HTMとしてIntel HaswellのRestricted Transactional Memoryを,グラフ問題としてDelaunay Mesh Refinementを取り上げ,提案する方法をpthreadsのmutexによる実装と比較して評価を行った.Nowadays, commodity processors are equipped with hardware transactional memory (HTM). Speculative parallel execution, which HTM adopts, is known to bring a performance gain in a wide range of graph algorithms. Therefore, the application of HTM to parallel graph processing seems promising. However, transactions in parallel graph processing for practical graph problems tend to be long because both graph traversal and updating have generally to be atomic. Executing such transactions efficiently is difficult because of hardware restrictions of HTM. To resolve this problem, we propose a method for shortening transactions of HTM. It makes calculation and graph traversal migrate from transactions and performs only graph updating within transactions. In this study, we use the Restricted Transactional Memory, which is a HTM functionality of the Intel Haswell architecture, and deal with Delaunay Mesh Refinement as an example graph problem. We evaluate the proposed method by comparing it with mutex locks in Phreads., 出版日 2015年06月02日, 情報処理学会論文誌プログラミング(PRO), 8巻, 1号, 掲載ページ 16-16, 日本語, 1882-7802, 170000147333, AA11464814
  • 低優先度処理を指定可能なリアルタイム処理向けI/Oスケジューラ
    高村 成道; 鵜川 始陽; 岩崎 英哉
    近年,リアルタイム性を必要とし,停止できない Web サービスが増加している.それらのメンテナンス処理はサービスを継続した状態で行う必要がある.このようなメンテナンスをオンラインメンテナンスと呼ぶ.オンラインメンテナンスの例には,データの集計や削除がある.オンラインメンテナンスを行う上で,メンテナンス処理の I/O 負荷が Web サービスに悪影響を及ぼすことが問題となっている.たとえば,データベースサーバ上の数百 GB のログファイルを削除するメンテナンスをオンラインで行う場合,大量の I/O 処理が行われデータベース処理が長時間停止するという事態が生じる.このような問題を解決するために,本研究ではメンテナンスの I/O 処理の実行をゆっくりと行う機構を提案する.Linux においては,I/O 処理の実行順序は I/O スケジューラが決定する.そこで,リアルタイム性を必要とする Web サービスのバックエンドで用いられている I/O スケジューラに,低優先度処理を指定する機能を追加した.実験用のデータベースサーバ上で本機構を評価したところ,既存の I/O スケジューラではデータベースと関係のない I/O 処理の実行中にデータベースのスループットが 30%以下に低下したのに対し,提案する I/O スケジューラでは 75%以上となった.The availablity of web services has been incresingly demanded. To achieve high availablity, database servers used in the backends of web services have to respond in a low latency. Maintenance operations (e.g., deleting log files and mining data) executed by an operator may raise a pressure on I/O subsystem, which increases the latency of database processing. To solve this problem, it is desired to execute maintenance operations in low priority. However, the deadline I/O scheduler, which is recommended for database servers on Linux cannot deal with priorities for I/O operations. In this research, we have extended the deadline I/O scheduler to enable us to assign low priority to a process, which is inherited to the children. Our I/O scheduler can suppress the increase of latency by executing the maintenance operations at low priority. We evaluated the usefulness of our I/O scheduler on a database server. While in the deadline I/O scheduler, maintenance operations degraded the throughput of database processing down to less than 30%, in our I/O scheduler they degraded that down to at most 75% by assigning low priority to maintenance operations., 一般社団法人情報処理学会, 出版日 2014年02月27日, 研究報告システムソフトウェアとオペレーティング・システム(OS), 2014巻, 8号, 掲載ページ 1-10, 日本語, 110009675775, AN10444176
  • Ruby on Railsにおけるテストケース自動生成の提案と実装'
    田代克也; 中野圭介; 岩崎英哉
    出版日 2013年03月, 第93回プログラミング研究発表会, 日本語
  • 高速な復帰が可能なLinuxのスリープ機構の実現
    羽田野大理; 岩崎英哉; 鵜川始陽
    近年データセンタでは,サーバの消費電力の増大が問題となっている.サーバの消費電力を抑えるには,例えばWebサーバではリクエストを処理し終えたら次のリクエストが到着するまでサーバをスリープさせるという手法が考えられる.しかし,現状のLinuxのスリープ機構はACPIを利用しており,スリープからの復帰に多くの時間がかかるという問題点がある.本研究では,ACPIを利用しないスリープ機構を作成した.このスリープ機構は,システム全体はスリープさせず,一部のデバイスのみをスリープさせ,CPUを簡易低電力状態にする.この方法で,Linuxのスリープを用いた場合と比較して,スリープからの復帰時間を大幅に削減できる事を確認した., 出版日 2013年02月21日, 研究報告システムソフトウェアとオペレーティング・システム(OS), 2013巻, 14号, 掲載ページ 1-8, 日本語, 110009550195, AN10444176
  • ビットマップマーキングを利用したマークコンパクトごみ集めのJikes RVMへの実装
    森川 和哉; 鵜川 始陽; 岩崎 英哉
    Jikes RVM上で,ビットマップマーキングを利用したマークコンパクトごみ集めを実装し評価した.マークコンパクトごみ集めで広く使われているLisp 2アルゴリズムでは,オブジェクトの移動処理のために,生きているオブジェクトをアドレス順に2回探索する.本手法は,オブジェクトの生存情報をビットマップを使って保持し,そのビットマップをスキャンすることによって,生きているオブジェクトを探索する.生きているオブジェクトが少ない場合,ビットマップ上ではゼロビットが連続しているため,この探索を高速化することができる.提案するごみ集めの性能をDaCapoベンチマークを用いて評価したところ,プログラムによっては,ヒープの使用率が低い場合に,Jikes RVMに標準で搭載されているマークコンパクトごみ集めよりも優れた結果を示した.We have implemented and evaluated a mark-compact garbage collection using bitmap marking on Jikes RVM. The Lisp 2 algorithm, which is widely used in mark-compact garbage colletion, searches twice for live objects in the address order. Our garbage collection holds the locations of live objects in the bitmap by marking their corresponding bits. Then it scans the bitmap for live objects. In the case where the number of live objects is small, the bitmap can be scanned quickly because it has long sequences of zero bits. According to the results of DaCapo benchmarks, our garbage collection is faster than the one that has been implemented on Jikes RVM, depending on programs and heap usage., 出版日 2013年01月24日, 情報処理学会論文誌プログラミング(PRO), 6巻, 1号, 掲載ページ 27-27, 日本語, 1882-7802, 110009517218, AA11464814
  • JavaScriptにおけるプログラム変換の効果
    田村知博; 中野圭介; 鵜川始陽; 岩崎英哉
    出版日 2012年01月06日, 情報処理学会夏のプログラミング・シンポジウム報告集, 2011巻, 掲載ページ 19-26, 日本語, 201202208058098881
  • 夏のプログラミングシンポジウム
    岩崎英哉; 川中真那; 小出洋; 田中哲朗; 松崎公紀; 三廻部大
    出版日 2012年01月06日, 第53回プログラミング・シンポジウム予稿集, 2012巻, 2012号, 掲載ページ 47-48, 日本語, 170000071246
  • 時間縮約によるステンシル計算の局所性最適化
    佐藤 重幸; 岩崎 英哉
    [日本ソフトウェア科学会], 出版日 2011年09月27日, 日本ソフトウェア科学会大会論文集, 28巻, 掲載ページ 1-16, 英語, 0913-5391, 40020660355, AN10158574
  • UECFS:SSDとHDDを併用して高速なファイルアクセスを実現するファイルシステム
    五味真幹; 鵜川始陽; 岩崎英哉
    出版日 2011年01月07日, 第52回プログラミング・シンポジウム予稿集, 2011巻, 掲載ページ 125-132, 日本語, 170000076314
  • 世代別Mostly-Copying GCのRuby VMへの実装と評価
    永原 治; 鵜川 始陽; 岩崎 英哉
    近年,Rubyによる大規模アプリケーションの開発が行われるようになってきている.大規模なアプリケーションの特徴として,大量のデータを扱い長時間動作し続けるという特徴があげられる.既存のRuby処理系は保守的マークスイープ方式でごみ集め(GC)をしているが,このような特徴を持つアプリケーションでは,世代別コピーGCでGCの時間を短縮できることが知られている.しかし,Ruby処理系には保守的GCを前提に作られている部分があり,移動できないオブジェクトが多くある.そのため,通常のコピーGCは実現できない.そこで,移動できないオブジェクトが存在しても,コピーGCを実現できるMostly-Copying GCを用いることにした.Mostly-Copying GCでは,ヒープを固定長のブロックに分割する.我々のGCでは,ブロックごとに世代を持たせる.マイナGCでは,新世代にある移動できるオブジェクトを旧世代に移動させるだけでなく,生存オブジェクトの多いブロックは,ブロックごと旧世代に含める.これにより移動できないオブジェクトも旧世代に移すことができる.Recently, large-scale applications have come to be developed in Ruby. A large-scale application tends to treat a large amount of data and to keep working for a long time. While the Ruby VM has the conservative mark-sweep GC, it is known that the time spent on GC in such an application can be reduced by using the generational copying GC. However, we cannot implement the copying GC in the Ruby VM, because part of the VM depends on the conservative GC, and many objects cannot be moved. Therefore we decided to use the mostly-copying GC, which collects garbage by copying only movable objects. The mostly-copying GC divides the heap into equal sized blocks. In our garbage collector, each block has a generation. In minor GC, the collector does not only move movable objects in the new generation to the old generation, but also turns blocks into the old generation if they contain many live objects. This allows immovable objects to get promoted., 出版日 2010年09月22日, 情報処理学会論文誌プログラミング(PRO), 3巻, 4号, 掲載ページ 61-61, 日本語, 1882-7802, 110007970960, AA11464814
  • プログラムの更新を可能とするCheckpoint/Restart機構
    室井 雅仁; 鵜川 始陽; 岩崎 英哉
    近年,連続的に利用されるシステムが広く普及したことに伴ない,予期せぬ実行時エラーに対処するため,耐故障性に関する研究がなされてきている.耐故障性に関する研究の一つとして,Checkpoint/Restart と呼ばれる手法がある.この手法は正常動作しているプロセスの状態を予め保存しておき,障害発生時に保存しておいた状態を復元する手法である.しかし,通常 Checkpoint/Restart は,同じプログラムを利用するプロセスへ保存した情報を復元するので,バグが原因の障害の場合,同じ障害が発生してしまう.そこで本論文では,バグを修正するなどプログラムの内容を更新したプロセスへ状態を復元することが可能な Checkpoint/Restart 機構の設計と実装を行った.提案機構を利用することで,予め保存した状態を更新後のプログラムを持つプロセスへ復元可能になり,バグの修正に本機構を利用することで,サービスを継続したままプログラムが原因の障害を防げることを確認した.Checkpoint/Restart is a well-known and useful technology for the recovery from a crash due to an unexpected runtime error. This technology first saves the snapshot of a process's running state, and if an error occurs, restores the snapshot to re-construct the state of the running process and resume the execution. However, Checkpoint/Restart usually restores a saved state to a process executing the same program used by the checkpointed process. Thus the same runtime error may occur in the future, since the bug is not fixed. To resolve this problem, this paper described the design and implementation of a Checkpoint/ Restart system which enables users to restore a snapshot to a process executing a program whose bug has been fixed. We have confirmed that the new system are able to prevents the restored process from suffering from the same runtime error., 情報処理学会, 出版日 2010年07月27日, 研究報告システムソフトウェアと オペレーティング・システム(OS), 2010巻, 3号, 掲載ページ 1-7, 日本語, 0919-6072, 110007995365, AN10444176
  • 世代別Mostly-Copying GCのRuby VMへの実装に向けて
    永原 治; 鵜川 始陽; 岩崎 英哉
    近年,Web アプリケーションをはじめとする Ruby による大規模アプリケーションの開発が行われるようになってきている.大規模なアプリケーションの特徴として,大量のデータを扱い長時間動作し続けるという特徴があげられる.既存の Ruby 処理系は保守的マークスイープ方式でごみ集め (GC) をしているが,このような特徴を持つアプリケーションでは,世代別コピー GC で GC の時間を短縮できることが知られている.しかし,Ruby 処理系には保守的 GC を前提に作られている部分があり,移動できないオブジェクトがあるため,通常のコピー GC は実現できない.そこで,移動できないオブジェクトが存在しても,コピー GC を実現できる Mostly-Copying GC を用いることにした.本研究では,世代別 Mostly-Copying GC の実装による GC 時間の短縮を目標として,Ruby1.9 の VM に Mostly-Copying GC の実装を行い,Ruby on Rails 組み込みの Web サーバなどを対象に移動できないオブジェクトの数やその寿命など世代別 GC の設計に必要なデータ収集を行った.その結果,移動できないオブジェクトの割合は少なくないが,それらは長寿命であるという傾向が分かった.本発表では,これらのデータを基に世代別 Mostly-Copying GC の実装方針と設計について述べる.Recently, large-scale applications, such as web applications, have come to be developed in Ruby. A large-scale application tends to treat a large amount of data and to keep working for a long time. While the Ruby VM has the conservative mark-sweep GC, it is known that the time spent on GC in such an application can be reduced by using the generational copying GC. However, we cannot implement the copying GC on the Ruby VM, because part of the VM depends on the conservative GC, and some objects cannot be moved. Therefore we decided to use the mostly-copying GC, which collects garbage by copying only movable objects. In this research, we aim to reduce the time spent on GC by implementing the mostly-copying GC on the VM of Ruby 1.9. We implemented the mostly-copying GC on the VM and examined the behavior of objects in the heap, such as the ratio of immovable objects and their lifetime, using the VM and a web server program of Ruby on Rails. As a result, we found immovable objects tend to be long-lived though the ratio of them is not small. In this presentation, we present the design of generational mostly-copying GC based on the observation., 出版日 2010年03月16日, 情報処理学会論文誌プログラミング(PRO), 3巻, 2号, 掲載ページ 49-49, 日本語, 1882-7802, 110007970976, AA11464814
  • メソッド実行委託を用いたRubyプロセスの負荷分散ライブラリ
    川ノ上 哲規; 岩崎 英哉; 鵜川 始陽
    プロセスの動的な負荷を分散するための手法として,スレッドマイグレーションがある.しかし,Ruby の処理系はプロセス実行時に C のスタックを使うため,Ruby ではスレッドマイグレーションの実現は難しい.そこで本発表では,メソッド実行委託という負荷分散の機構を提案し,Ruby のライブラリとして実装する.メソッド実行委託とは,メソッドの実行に必要なオブジェクトとクラス定義を,呼び出し時に選んだ別の計算機上のプロセスに動的に転送して実行させることで,負荷を分散する機構である.メソッド実行を請け負うプロセスは,本機構によって自動的に決定されるため,プログラマは請負先の明示的な記述をする必要はない.このライブラリを用いれば,既存の Ruby プログラムに対して,委託用コードを簡単に付加することができ,負荷分散を考慮したプログラムを Ruby で簡潔に記述できる.本発表では,JPEG 圧縮の計算における負荷の分散,クライアント・サーバ型アプリケーションにおけるサーバプロセスの負荷分散をするプログラムを用いて,提案機構の有効性についても述べる.Thread migration is a well-known technique for load balancing. However, since a RubyVM uses a C stack in runtime, it is difficult to implement a thread migration on Ruby. To cope with this problem, we propose a load distribution framework named "method entrusting" and implemented it as a library. The method entrusting dynamically chooses another process on another computer and entrust the process with a method invocation by transferring objects and class definitions, if necessary, that are indispensable for the invocation. The framework automatically selects an appropriate process that contract the method execution. Thus, programmers are not required to specify the process explicitly in their programs. This library enables programmers to easily add codes for method entrusting into existing Ruby programs and to easily achieve load balancing. In this presentation, we also show the effectiveness of this framework with a program for JPEG compression and a program for load distribution on server processes in a client-server application., 出版日 2009年08月28日, 情報処理学会論文誌プログラミング(PRO), 2巻, 4号, 掲載ページ 66-66, 日本語, 1882-7802, 110007970922, AA11464814
  • 並列計算パターン (スケルトン) による並列プログラミング
    岩崎英哉; 胡振江
    出版日 2008年12月, 情報処理, 49巻, 12号, 掲載ページ 1385-1394, 日本語, 記事・総説・解説・論説等(その他)
  • スケルトン並列プログラミング
    胡振江; 岩崎英哉
    出版日 2005年10月, 情報処理, 46巻, 10号, 掲載ページ 1158-1162, 日本語, 記事・総説・解説・論説等(その他)
  • 助っ人:構成的な並列スケルトンによる並列プログラミングライブラリ
    松崎 公紀; 明石 良樹; 江本 健斗; 岩崎 英哉; 胡 振江
    並列プログラミングにおける, 通信, 同期, 資源の配置などの問題を解消する一つのパラダイムとして, スケルトン並列プログラミングが提案されている. 我々は, 並列スケルトンライブラリ「助っ人」を開発してきた. 助っ人の特徴としては, (1) 分散データ構造として, リスト, 木, 二次元配列をサポートしていること, (2) 構成的アルゴリズム論による最適化機構, が挙げられる. 本論文では, 具体例を交えて, 本ライブラリを紹介する., 日本ソフトウェア科学会, 出版日 2005年, 日本ソフトウェア科学会大会講演論文集, 22巻, 0号, 掲載ページ 320-333, 日本語, 130004638879
  • 最適化機構を持つC++並列スケルトンライブラリ
    明石 良樹; 松崎 公紀; 岩崎 英哉; 筧 一彦; 胡 振江
    並列プログラムを作成する難しさを緩和するため,頻繁に用いられる並列処理のパターンをあらかじめ実装しておき,そのパターンの組み合わせでプログラムを作成する「スケルトン並列プログラミング」が考案されている.プログラマは並列スケルトンと呼ばれる関数を組み合わせることによって,並列プログラムを容易に記述することができるようになる.しかし,並列スケルトンで書かれたプログラムは,必ずしも実行効率が良くないという問題点がある.本研究では,BMFという計算モデルに基づいた並列スケルトンライブラリをC++上に実装した.その上で,融合変換と呼ばれる,複数の関数呼び出しを単一の関数呼び出しに融合する手法を適用し,並列スケルトンで書かれたプログラムを最適化する機構を実現した.本発表では,並列スケルトンライブラリの実装を提案し,最適化の効果について報告する., 日本ソフトウェア科学会, 出版日 2004年, 日本ソフトウェア科学会大会講演論文集, 21巻, 0号, 掲載ページ 46-46, 1349-3515, 130005006607
  • ディペンダブルなインターネットサーバを構築するためのカスタマイズ可能なクラスタ用ツールキット
    杉木 章義; 河野 健二; 岩崎 英哉; 益田 隆司
    インターネットサーバでは,提供するサービスに対する高いディペンダビリティが求められている.そのため,可用性・信頼性・管理容易性等,お互いにトレードオフの関係にあるディペンダビリティの構成要因を,アプリケーションの特性や目的に応じて適切に調整する必要がある.既存のアプローチでは,特定のサービスに特化した方法でディペンダビリティを達成したきたが,汎用性に欠け,他のサービスにその方法が転用し難いという問題点があった.この問題点を解決するため,本発表では,サーバシステムをいくつかのステージに分割し,アプリケーションの特性に応じてそれぞれの段階をカスタマイズ可能とすることによりディペンダビリティの達成を可能とするようなツールキットを提案し,その実現を示す., 日本ソフトウェア科学会, 出版日 2003年, 日本ソフトウェア科学会大会講演論文集, 2003巻, 0号, 掲載ページ 11-11, 1349-3515, 130004638744
  • Segmented Diffusion Theorem (invited paper)
    Zhenjiang Hu; Tomonari Takahashi; Hideya Iwasaki; Masato Takeichi
    出版日 2002年, 2002 IEEE International Conference on Systems, Man and Cybernetics (SMC 02), Hammamet, Tunisia, October 6-9, 2002. IEEE Press.
  • プログラミング入門者のためのプログラミング言語「若葉」とその処理系
    吉良智樹; 並木美太郎; 岩崎英哉
    出版日 1999年07月28日, 情報教育シンポジウム1999論文集, 99巻, 10号, 掲載ページ 127-134, 日本語, 170000082005
  • 構成的アルゴリズム論
    岩崎英哉
    出版日 1998年11月, コンピュータソフトウェア, 15巻, 6号, 掲載ページ 57-70, 日本語, 査読付, 記事・総説・解説・論説等(その他)
  • 関数プログラムのプロモーション変換のための二手法の関係
    岩崎英哉; 胡振江
    関数プログラムでは, 関数の間で受け渡されるが最終結果には出現しない中間的なデータ構造を生成しないように, 関数合成をひとつの関数にプロモーションする(融合する)ことが, 効率改善にとって重要である. 補助引数あるいは蓄積引数を持つ関数に関してこの問題を解決するための手法として, "高階catamorphism"を用いる方法と, "媒介型"を導入することによるhylomorphismを用いる方法が研究されている. 本稿は, 補助引数を持つ関数の高階catamorphismによる融合操作は, 媒介型を用いた変換操作の枠組で説明することができることを, 簡単な具体例を通して示す., 社団法人情報処理学会, 出版日 1996年03月26日, 情報処理学会研究報告. PRO, [プログラミング], 96巻, 33号, 掲載ページ 79-84, 0919-6072, 110002929510
  • 平面上の矩形和の最大値問題の並列プログラムの導出
    胡 振江; 岩崎 英哉; 武市 正人
    List Homomorphismは, 理想的には分割統治アルゴリズムに適しており, 並列プログラミングの分野で最近注目を集めているが, 従来の議論はアドホックに行なわれる傾向があった. 本稿では, 「平面上の矩形和の最大値問題」を例題として, 素朴で効率の悪いプログラムから効率のよい並列プログラムを系統的・形式的に導出する方法を報告し, List Homomorphismの再帰的構造に基づいて定義されるTuplingとFusionというふたつの変換技法を提案する., 一般社団法人情報処理学会, 出版日 1996年03月26日, 情報処理学会研究報告. PRO, [プログラミング], 96巻, 33号, 掲載ページ 73-78, 英語, 110002929509
  • Cheap Tupling Transformation
    Zhenjiang Hu; Hideya Iwasaki; Masato Takeichi
    出版日 1996年, Technical Report METR 96-08, University of Tokyo. October 1996
  • 再帰的に定義された関係からのアルゴリズムの導出
    徐 良為; 武市 正人; 岩崎 英哉
    関係は数学的に扱いやすいいろいろな性質をもっているので,関係を用いてプログラムの仕様と実現の両方を定義することができる.つまり,関係を入力値と出力値の間の論理式と見なすときに,それを仕様として使うことができ,関係を再帰的に定義された他の関係の合成と見なすときに,そのを実現の記述として使うことができる.本論文では,関係の再帰定義のスキームを導入し,その性質について述べる.また,それを利用して,GAMMAアルゴリズムモデルを書き換え,例を通じてプログラム変換技術についても述べる., 一般社団法人情報処理学会, 出版日 1994年03月18日, 情報処理学会研究報告. 記号処理研究会報告, 94巻, 31号, 掲載ページ 17-24, 英語, 110002929460
  • Catamorphismに基づく関数プログラムの変換
    胡振江; 岩崎英哉; 武市正人
    Accumulationとは,構造を持つデータに対する計算を,途中経過を保持しつつ進めていく方法であり,逐次・並列を問わず,効率の良いプログラムの設計・記述によく用いられる.本論文では,Accumulationを定式化するために,従来のCatamorphismの考えを拡張した高階Catamorphismを提案する.また,高階Caramorphismを用いて記述されたプログラムの実行効率を改善するための,基本的な変換定理(プロモーション定理)を示す.さらに,具体的な変換手順を,いくつかの例とともに示す., 社団法人情報処理学会, 出版日 1994年03月09日, 情報処理学会研究報告. [プログラミング-言語基礎実践-], 94巻, 21号, 掲載ページ 49-56, 0919-6072, 110002929444
  • Catamorphismに基づく関数プログラムの変換
    胡 振江; 岩崎 英哉; 武市 正人
    Accumulationとは,構造を持つデータに対する計算を,途中経過を保持しつつ進めていく方法であり,逐次・並列を問わず,効率の良いプログラムの設計・記述によく用いられる.本論文では,Accumulationを定式化するために,従来のCatamorphismの考えを拡張した高階Catamorphismを提案する.また,高階Caramorphismを用いて記述されたプログラムの実行効率を改善するための,基本的な変換定理(プロモーション定理)を示す.さらに、具体的な変換手順を、いくつかの例とともに示す., 一般社団法人電子情報通信学会, 出版日 1994年03月09日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 93巻, 496号, 掲載ページ 49-56, 英語, 110003207093

書籍等出版物

  • 情報科学の基礎-新しい情報リテラシをめざして-
    山口和紀; 岩崎英哉
    日本語, 共著, 昭晃堂, 出版日 2006年04月
  • エンサイクロペディア情報処理 改訂版
    情報処理学会編
    日本語, 共著, オーム社, 出版日 2000年
  • エンサイクロペディア情報処理
    情報処理学会編
    日本語, 共著, オーム社, 出版日 1994年

講演・口頭発表等

  • ページ遷移・レイアウト・スクリプトを分離した Web アプリケーション記述システム
    廣田幸一; 岩崎英哉
    シンポジウム・ワークショップパネル(公募), 日本語, 第9回プログラミングおよびプログラミング言語ワークショップ (PPL'2007), 日本ソフトウェア科学会 第9回プログラミングおよびプログラミング言語ワークショップ (PPL'2007)
    発表日 2007年03月
  • Improving Sequence を第一級の対象とする Scheme コンパイラ
    高野保真; 岩崎英哉
    シンポジウム・ワークショップパネル(公募), 日本語, 第8回プログラミングおよびプログラミング言語ワークショップ (PPL'2006), 日本ソフトウェア科学会 第8回プログラミングおよびプログラミング言語ワークショップ (PPL'2006), 大津
    発表日 2006年03月
  • ディペンダブルなインターネット・サーバを実現するクラスタ用ミドルウエアの基本設計
    杉木章義; 河野健二; 岩崎英哉; 益田隆司
    シンポジウム・ワークショップパネル(公募), 日本語, 先進的計算基盤システムシンポジウム (SACSIS 2003), 情報処理学会 先進的計算基盤システムシンポジウム (SACSIS 2003)
    発表日 2003年05月
  • 需要変化に動的に対応するミラーサーバの管理基盤
    揚妻匡邦; 河野健二; 岩崎英哉; 益田隆司
    口頭発表(一般), 日本語, 日本ソフトウェア科学会 第6回プログラミングおよび応用のシステムに関するワークショップ (SPA'2003)
    発表日 2003年03月
  • 不均等データ上における汎用的並列スケルトン s-diff の提案
    高橋知成; 胡振江; 岩崎英哉
    口頭発表(一般), 日本語, 日本ソフトウェア科学会 第4回プログラミングおよびプログラミング言語ワークショップ (PPL'2002)
    発表日 2002年03月
  • C言語上のスケルトン並列プログラミングシステム
    白沢楽; 胡振江; 岩崎英哉
    口頭発表(一般), 日本語, 日本ソフトウェア科学会 第5回プログラミングおよび応用のシステムに関する ワークショップ (SPA'2002)
    発表日 2002年03月
  • プログラム設計を支援する学習環境 Soegi
    松崎公紀; 岩崎英哉
    シンポジウム・ワークショップパネル(公募), 日本語, 情報処理学会 夏のプログラミング・シンポジウム 「プログラミングの鉄人---プログラミングの技」報告集
    発表日 2001年08月

所属学協会

  • ACM
  • 情報処理学会
  • 日本ソフトウェア科学会

共同研究・競争的資金等の研究課題

  • システムソフトウェアのための安全性と記述性に優れた領域特化言語とその構成法
    岩崎 英哉; 中山 泰一
    日本学術振興会, 科学研究費助成事業, 明治大学, 基盤研究(C), 23K11055
    研究期間 2023年04月01日 - 2026年03月31日
  • 大規模グラフを対象とする並列分散処理プログラムのプログラム変換技法に基づく開発手法の確立
    岩崎英哉
    研究期間 2019年04月01日 - 2021年03月31日
  • IoTデバイス向けの軽量でモジュラーなJavaScript処理系
    鵜川 始陽; 岩崎 英哉; 高野 保真
    日本学術振興会, 科学研究費助成事業, 高知工科大学, 基盤研究(C), Internet of Things(IoT)で用いられる組込みシステム向けの軽量なJavaScript仮想機械(VM)を開発するために、アプリケーションに特化したJavaScriptサブセットのVMを自動生成するという方針で研究を行い、次の成果を得た。(1)演算子のオペランドの一部のデータ型だけを受け取るように特化したVMを自動生成する仕組みおよび最適化アルゴリズム。(2)コンパクションを行うごみ集めのアルゴリズムとその実装の検査手法。(3)弱いメモリモデルのCPU上での動作を検証するためのモデル検査ライブラリ。これらの成果はJavaScript VM生成系eJSTKに実装した。, 16K00103
    研究期間 2016年04月01日 - 2019年03月31日
  • 大規模グラフ並列処理のための代数的構造に基づく理論基盤とプログラム開発基盤の構築
    岩崎英哉
    研究期間 2014年04月01日 - 2018年03月31日
  • マルチコア・メニーコア組込みシステム向け言語仮想機械のメモリ管理
    鵜川 始陽; 岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 基盤研究(C), 本研究では,マルチコアやメニーコアプロセッサを使った組み込みシステムで動作する言語仮想機械に適したごみ集め(GC)の開発を行った.本研究では主に以下の成果を得た.(1)実時間アプリケーションに適した既存の並行コピーGCを実装し問題点を発見して改良した.(2)それを基にして新しい並行コンパクションGCを開発した.(3)GCの消費電力を削減する手法を開発した.(4)バグを発見するプログラム解析ツールを開発した., 25330080
    研究期間 2013年04月01日 - 2016年03月31日
  • 実用的ウェブアプリケーション開発を支援するサーバサイドJavaScript処理系
    岩崎英哉
    研究期間 2011年04月01日 - 2014年03月31日
  • 多様な形態の密結合マルチコアアーキテクチャ向け並列プログラミングシステム
    岩崎英哉
    研究期間 2008年04月01日 - 2011年03月31日
  • 多様なデータ型と最適化機構をサポートする本格的スケルトン並列ライブラリの構築
    岩崎 英哉; 胡 振江
    日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 本研究は,効率的な並列プログラムを逐次的な感覚で作成することを支援する,実用的な「スケルトン並列ライブラリ」の開発を目指したものである.スケルトン並列プログラミングでは,典型的な並列処理パターン,たとえば,すべてのデータに同一の関数を適用するmap,データ間に二項演算子を挟んで計算するreduce, reduceの途中結果も残すscanのような「並列スケルトン」と呼ばれる基本関数を組み合わせてプログラムを作成する.各並列スケルトンは,目的とする並列構造を抽象化しているので,利用者はその内部の詳細を知る必要はない.その結果,並列スケルトンを用いれば,並列アルゴリズムや並列アーキテクチャの深い知識を必要とせず,逐次プログラムを書く感覚で並列プログラムを開発することができる. 本研究を遂行することにより,スケルトン並列ライブラリSkeTo(助っ人)を開発し,一般に公開する(URLはhttp://www.ipl.t.u-tokyo.ac.jp/sketo/)に至った.SkeToは,従来のスケルトンライブラリには見られない以下の特徴を持つ. ・リスト(一次元配列)のみならず,行列(二次元配列),二分木,Rose木(分岐数が一定でない木)といった,多様なデータ型をサポートしている. ・C++をベースとしているが,C++の構文に一切拡張を加えていないため,通常のC++プログラムを書くことができる利用者ならば,障壁なくプログラムを開発できるように設計されている. ・構成的アルゴリズム論という理論的基礎の上に立ち,並列スケルトンの連続した呼び出しをひとつにまとめるという最適化機構を備えている., 17500021
    研究期間 2005年 - 2006年
  • 需要変化に動的に対応するインターネットサービスの自己組織化サーバ群による実現
    益田 隆司; 河野 健二; 岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 本研究は,クライアントからの需要に応じて,サーバの数や配置に関する自己組織化を適切に行い,常に最適なサーバ構成を実現するような基盤ソフトウェア技術を確立することを目的とする.本研究の目的を達成するためには,サーバ側の基本機構,およびクライアント側におけるサーバ選択の基本機構を両方を確立しなければならない.今年度は,主にサーバ側の基本機構について研究を行い,以下のような成果を得ることができた. ・サーバ配布機構の実現 モバイルコード技術を用いて,サーバおよびコンテンツを効率よく配布するための実装技術を開発した. ・サーバの最適配置手法の確立 動的な負荷変動に応じて,サーバの配布・回収の方針を定めるアルゴリズム,負荷の分布に応じて最適な配置を可能とするアルゴリズムを設計し,シミュレーションによりその効果を確認し,実インターネット環境への実装を行った. ・デイペンダブルなサーバの構成方法の提唱 「信頼できる」デイペンダブルなサーバを構成するためのソフトウェア的構成方法について検討し,サーバ用ツールキットを試作し,ある程度の効果を確認した., 15500034
    研究期間 2003年 - 2004年
  • スケルトン並列プログラミングの新しい基盤構築とシステムの実用化
    岩崎 英哉; 胡 振江
    日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 本研究は,効率のよい並列プログラムを作成するには,並列アルゴリズムや並列アーキテクチャの深い知識を必要とし困難を伴う,という問題点を克服することを目標として,「並列スケルトン」と呼ばれる基本関数を部品として組み合わせて並列プログラムを作成する「スケルトン並列プログラミング」に焦点をあて,理論的基盤の構築,実用的なシステムの開発を目指したものである. 本研究によって得られた成果として, 1)リストのみならず木構造のような再帰データ構造も対象とし,スケルトンの適切な選択と組合せを抽象化するような並列スケルトンの開発と実用化, 2)プログラム運算の発想に基づく,スケルトンの組合せの最適化手法の開発と実用化. 3)C++とMPIを利用した,一般的な並列実行環境をベースとしたスケルトン並列ライブラリシステムの開発と実用化, をあげることができる. 作成したライブラリは,a)従来から提案されているデータ並列のスケルトンに加え,典型的な再帰関数を抽象化したaccmulateスケルトンも提供している,b)余計な中間データ構造を生成させない「融合変換」と呼ばれるプログラム最適化の機構を(ある程度)備えている,といったような,既存のシステムにないいくつかの特長を持っている.さらに,C++に言語的な拡張を一切加えず,標準的な並列ライブラリであるMPIをベースに作動するため,きわめて汎用性に富んでいる., 15500020
    研究期間 2003年 - 2004年
  • プログラミングからプレゼンテーションまでの初心者一貫教育環境の実現
    岩崎 英哉; 並木 美太郎
    日本学術振興会, 科学研究費助成事業, 基盤研究(C), 本研究は,プログラミング能力,ドキュメンテーション能力,プレゼンテーション能力の三つを不可分なものと考え,初心者に対するこれらの効果的な学習を支援し論理的思考能力を養う計算機環境の構築を目的とした.特に,初心者学習の支援を強化したシステム,あるいは,初心者学習に特化したシステムを目指し,プログラミング方法論と言語処理系に関する研究,自然言語処理技術の応用研究などにも重点を置いた.その結果,次のような成果を得ることができた. 1.初心者学習環境の提案 初心者の問題解決の論理設計を図形表現を用いて支援し,コーディング・簡単なドキュメント作成をも支援する学習環境を構築した.また,ブラウザ上で作動し,実行時の変数内容の表示,構文エラー・実行時エラーに対するデバッグ支援等を行うシステムをJavaを用いて実現した. 2.プログラミング方法論からのプログラミング支援 プログラムの定型的な処理をパターン化した「スケルトン」を用いるプログラミング方法論の基礎的な研究を行い,その成果を生かしたスケルトンプログラミングシステムを構築した. 3.プレゼンテーション支援環境の提案 文書を入力とし,キーワード抽出,短文分割,体言止めなどの自然言語処理の諸技術を組み合わせ,プレゼンテーションシートの「たたき台」を自動生成するシステムを試作した. 4.ドキュメンテーション支援環境の提案 高品質なドキュメンテーション作成を支援するため,同音異義語誤りを検出し代替候補を提示するようなシステムを作成した.さらに,プログラミング言語の提供する機能と文書作成システムを融合して効率的なドキュメンテーション作成を可能とするシステムを構築した., 12680330
    研究期間 2000年 - 2001年
  • プログラム運算システムの設計および実現に関する研究
    武市 正人; 岩崎 英哉; 胡 振江; 尾上 能之
    日本学術振興会, 科学研究費助成事業, 東京大学, 基盤研究(B), 本研究は、プログラムを効率的に操作することのできるプログラム運算システムを開発しようとするものである。本国際学術共同研究では、構成的アルゴリズム論の創始者であるRichard Bird教授と、それに着目して実用システムの検討を進めてきている代表者(武市正人)の両者のグループで緊密な連携をとって、研究を進め、理論的考察を深めるとともに、工学的に実用的なシステムを構築することを目的とした。 本研究の最終年次である本年度は、これまでの共同討議をもとに、構成的アルゴリズム論の理論的基礎に基づく運算システムの具体的な設計を行ない、実現したシステムをWEBを通じて公開した。 本研究の期間を通じて、とくに、Allegoryにおいて変換を構造化する手法(Bird, Gibbons担当)、部分計算・並列化などの変換を構造化する手法(武市、胡担当)、それらの実現法に関する検討(岩崎、尾上担当)、変換モジュールの効率的な統合に関する研究(de Moor,胡担当)、変換システムの漸増的機能強化に関する研究(武市、胡担当)、これまでに開発した融合変換システムHYLOの改良(岩崎、尾上担当)などの研究で成果をあげることができた。 一昨年、昨年には、ワークショップを開催するなど、関連分野の研究者にも参加を求めて成果を発表したが、本年度の研究の推進にあたっては、2002年2月に東京において、Oxfordの研究者と最終取りまとめを行ない、研究を総括した。 3年間の成果報告として、ワークショップ記録、および討議資料をまとめ、関連研究者に配布した。, 11694130
    研究期間 1999年 - 2001年
  • 構成的並列プログラミングモデルの設計及び実現に関する研究
    武市 正人; 岩崎 英哉; 胡 振江; 尾上 能之
    日本学術振興会, 科学研究費助成事業, 東京大学, 基盤研究(B), 本研究では、プログラム変換システムの構築に有効な理論として知られている構成的アルゴリズム論を基礎として、新しい並列プログラミングモデルと言語を提案し、並列計算機を意識することなく、抽象的なレベルで並列プログラムを開発することができるような枠組みを与え、それを実現するプログラミングシステムを構築することを目的としている。 平成11年度〜12年度には、構成的アルゴリズム論に基づいて並列プログラミングのための並列Skeletonを設計したが、平成13年度は、それに基づいて具体的な並列システムとしてPCクラスタによる分散並列システムを構築し、言語処理系の基本設計と実験を行なった。研究にあたっては、構成的アルゴリズム論に基づく並列システムに依存しない並列Skeletonの設計(武市/胡)、PCクラスタの並列計算システムの構築(岩崎/尾上)、のように役割分担を行ない、密接に連携をとって協調して推進した。 並列Skeletonの実現にあたっては、あらたな手法としてのDiffusionの概念を提唱するとともに、その実現方式を考察し、研究成果を国際会議で報告した。並列言語処理系の実験環境に関しては、標準的なMPIライブラリを用いて並列プリミティブを実現し、いくつかのプログラムを用いて評価した。 これらの成果により、従来の発見的・経験的な並列化手法に比べて並列化の過程を自動的に行なう方法として望ましいことを確認した。, 11480065
    研究期間 1999年 - 2001年
  • プログラム運算システムの実用化に関する研究
    武市 正人; 尾上 能之; 田中 哲朗; 胡 振江; 高野 明彦; 岩崎 英哉; 高野 昭彦
    日本学術振興会, 科学研究費助成事業, 東京大学, 基盤研究(B), 本研究では、構成的アルゴリズム論に基づいてプログラムの最適化を行なうための枠組みを設計するとともに、従来、発見的な手法で実現されていたプログラム変換システムに見られた非決定性を含む変換アルゴリズムを除去し、実用的なプログラム変換システムを構築しようとするものである。そこでは、代数的な規則に基づいて、系統的にプログラムを変換する手法を提案し、それを実現するための変換アルゴリズムの定式化を行なった。構成的アルゴリズム論に基づくプログラムの運算手法として、組変換(tupling)、融合変換(fusion)、並列化(parallelization)などの成果を得ている。 昨年度、一昨年度には、これらの変換規則をもとに、プログラムの融合変換システムのプロトタイプを作成し、その効果を確認して実用化システムの実現可能性を評価した。 本研究の最終年度である本年度はこれらの検討をもとに、プログラム融合変換システムHYLO Calculatorを関数型プログラム言語処理系Haskellに組み込み、実用的な変換システムとして実現した。実用規模のベンチマークプログラムを用いて、有効性の検討を行なった結果、実行時のメモリ使用量において、最大23%減という効果が見られた。,このシステムにより、実用規模のプログラムに対して融合変換の有効性が確認され、システムをインターネットを通じて公開して、国内外の研究者等の利用に供している。, 10558041
    研究期間 1998年 - 2000年
  • 一般的な再帰構造をもつ関数プログラムの融合変換とその実用化
    岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 東京大学, 特定領域研究(A), 本年度は,主として次のような研究を進めた. 1. 融合と組化という二つのプログラム変換手法を有効に組合わせることによる,系統的な変換の実現. 2. 相互再帰の定式化という前年度の研究成果を実働システムとして役立てるための,データ構成子の抽象化手法の検討. 前者に関する主要な成果は,複数の独立したプログラム変換手法,具体的には融合(Fusion)と組化(Tupling)を順番に適用することにより,プログラムを効率のよいものへ系統的に変換可能であることを示すことができた点である.この手法を,一/二次元最大部分列和/積問題に適用し,その有効性を確認した. 後者については,構成的アルゴリズム論における代表的な融合定理(酸性雨定理)を適用可能とするための,変換対象関数の静的解析に関して研究を進めた.「色情報」も付加して型検査を行うことにより,従来のアルゴリズムでは抽象化できなかった,相互再帰定義された型のデータ構成子についても解析が可能になるとの見通しを得た. この他,プログラム変換システムを試作段階から実用的な段階へと推し進める研究も行った., 10139210
    研究期間 1998年 - 1998年
  • S式指向のプログラミングシステムの構築に関する研究
    岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 奨励研究(A), 本研究では,Lispの一方言であるUtiLispをベースとしている.本年度は,主として次のような研究を進め,成果を得ることができた. 1. UtiLispの処理系を,インタプリタ本体にはほとんど手を入れず,様々な環境で作動可能し,さらに移植性の高いGUI(Graphical User Interface)を開発する研究を行った.具体的には,Unix環境とWindows環境の双方で作動するようなGUIを具備するUtiLispシステムを構築し,性能・移植性等について良好な結果を得ることができた. 2. Lispのような記号処理言語あるいは関数型言語的な側面と手続き型言語的な側面を併せ持つ初心者入門用言語環境を設計・実現した.このシステムはJava仮想機械へのコンパイラであり,これにより,ネットワーク指向,機種非依存という特長を備えている. 3. 記号処理プログラム・関数プログラムを,より実行効率のよいものに静的に変換するための手法に関する研究を行った.具体的には,複数の独立したプログラム変換手法(融合(Fusion)と組化(Tupling))を順番に適用することにより,プログラムを効率のよいものへ系統的に変換可能であることを示し,一/二次元最大部分列和/積問題に適用してその有効性を確認した., 09780254
    研究期間 1997年 - 1998年
  • 構成的アルゴリズム論に基づくプログラム最適化とその実現法に関する研究
    武市 正人; 胡 振江; 高野 明彦; 田中 哲朗; 岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 東京大学, 基盤研究(C), 本研究では、構成的アルゴリズム論に基づいてプログラムの最適化を行なうための枠組みを設計するとともに、従来、発見的な手法で実現されていたプログラム変換システムに見られた非決定性を含む変換アルゴリズムを除去し、実用的なプログラム変換システムを構築しようとするものである。そこでは、代数的な規則に基づいて、系統的にプログラムを変換する手法を提案し、それを実現するための変換アルゴリズムの定式化を行なった。構成的アルゴリズム論に基づくプログラムの運算手法として、組変換(tupling)、融合変換(fusion)、並列化(parallelization)などの成果を得た。 本年度は平成9年度に得られた成果をもとに、構成的アルゴリズム論に基づくプログラム最適化の定式化を完了させるとともに、効率のよいプログラムを開発するためのプログラム変換システムのプロトタイプを構築し、その有効性の評価を行なった。プログラム最適化で扱われるプログラム変換には、効率のよいプログラムへの変換、逐次プログラムから並列プログラムへの変換などであるが、プロトタイプにはそのうちで、効率向上を目的とする融合変換を実現した。, 09680326
    研究期間 1997年 - 1998年
  • 関数プログラムの再帰構造の抽象化とプログラム融合変換に関する研究
    岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 東京農工大学, 重点領域研究, 構成的手法によるプログラム変換では,プログラムや型定義を数学的な対象として扱い,少数の強力な変換定理を用いてプログラムを効率のよいものに変換していく.本研究では,従来は十分な考察がなされていなかった相互再帰などの複雑な再帰構造を対象とし,その定式化・変換定理などの実用面における考察を行った. そのために,単純再帰の場合の(一引数の)通常の関手の拡張である二項関手(二引数の関手)を用いて相互再帰を定式化するアプローチをとり,次のような成果を得ることができた. ・二項関手への拡張に対応し,Catamorphism,Anamorphism,Hylomorphismなどのプログラム標準形を拡張した. ・この拡張は「自然な」拡張になっているので,従来の単純な再帰の場合の融合変換定理が,同じ形の式を保ったまま成立することが示された. ・単純な再帰関数のtuple(組)は,相互再帰の特殊な場合として捉えることが可能であることが判明した.したがって,同一のデータ構造を複数回辿るのを防ぐのに有効とされる「tupling」と呼ばれる技法(の一部)は,二項関手を用いた相互再帰の枠組の中に統合することが可能である., 09245207
    研究期間 1997年 - 1997年
  • プログラムの自己進化機構とその実現法に関する研究
    武市 正人; 田中 哲朗; 金子 敬一; 岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 東京大学, 基盤研究(B), 本研究は、プログラム自体が実行環境に応じて進化してゆく機構を追求することである。通常の計算機プログラムが、問題領域を構成する要素をモデル化して表現したデータを扱って結果を得ることを目的としているが、本研究では、このような計算を行なうプログラム自体を進化させ、改良してゆく機構を考察することが目的である。 昨年度には、関数プログラムの完全遅延評価機構が自己最適化の効果をもっていることを発見し、それに基づいた部分計算機構の実現と実験による検証を行なったが、本年度は、統一的な視点から、プログラムの最適化の方法を追求し、構成的アルゴリズムに基づくHylomorphismによるプログラムの変換手法を確立した。そこでは、データ型と再帰構造に着目して、発見的手法によらないプログラムの変換システムを構築し、有効性を確認している。従来のプログラム変換が再帰や繰返しの構造に基づいて考えられていたものに対して、データ構造とそれを扱うプログラムの構造を一体として捉えるところにその特徴がある。この成果は、プログラム自体が環境に適応して進化するためのプログラム構造を捉える上で重要なものと考えられる。 以上の成果は、自己進化機構の基礎となる研究として主として、国際学会で発表している。これらをもとに、来年度より発足予定の重点領域研究「ソフトウェアの発展機構の研究」でさらに発展させる予定である。, 07458053
    研究期間 1995年 - 1996年
  • 並列計算機上の関数プログラミングシステムの構築に関する研究
    武市 正人; 田中 哲朗; 松岡 聡; 岩崎 英哉; 米澤 明憲
    日本学術振興会, 科学研究費助成事業, 東京大学, 基盤研究(A), 本研究は、並列計算機上に関数プログラミングシステムを構築して、あらたな規範に基づく並列プログラミングの支援環境を与えようとするものである。 一昨年度より開発を進めてきた並列計算機AP1000上の関数プログラミングシステムParallel Goferを用いてさまざまな並列アルゴリズムを実現したプログラムを用意し、評価しつつコンパイラの最適化を進めてきた。 この研究を進めてゆく過程で、関数プログラミングシステムにおけるデータのUnbox化の重要性が明らかになってきた。データを動的に生成するという関数プログラムの実行においては、生成するデータの効率のよい取扱いがきわめて重要になってくる。ここでは、データのUnbox化に関して、動的にヒ-プ上に生成するとされるデータのうちで、実際にはそうする必要のないものを検出する方法を提案して実現し、評価した。本年度には、このようなデータのUnbox化とともに、構成的アルゴリズムに基づくHylomorphismによるプログラムの変換システムを構築し、有効性を確認した。これらは、並列関数プログラムに固有のものではなく、広く関数プログラミングシステムに適用できる手法である。 以上の研究成果は、主として、国際学会で発表しているが、これらをもとにして実現した並列関数プログラミングシステムはネットワークでアクセスできる形で公開する予定である。, 06558039
    研究期間 1994年 - 1996年
  • 構成的手法によるプログラムの効率化に関する研究
    岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 東京大学, 奨励研究(A), 構成的手法によるプログラム変換では,プログラムや型定義を数学的な対象として扱い,少数の強力な変換定理を用いてプログラムを効率のよいものに変換していく.本研究では,関数プログラムをその対象とし,構成的手法を用いたプログラムの効率化の可能性について考察し,以下のような結果を得た. ・構成的手法においてはcatamorphismと呼ばれる範疇の関数(プログラム)が重要な役割を果たすが,従来のcatamorphismだけでは記述できないようなプログラムに関しても型変換の前処理を施すことによってcatamorphismの枠組に入れることができることを示した. ・上の「型変換」はcatamorphismとは双対の関係にあるanamorphismの範疇に入るものになり,その結果,元の(変換前の)プログラムはcatamorphismとanamorphismの合成,すなわちhylomorphismで表現されることが判明した. ・hylomorphismに対する変換定理を適用しやすくするための,hylomorphismを「再構成」する変換アルゴリズムを確立した. ・従来のcatamorphismを高階関数に拡張するというという「高階catamorphism」の考えは,上で述べた型変換の前処理と密接な関係にあることが判明した. 以上によりhylomorphismが,構成的手法の見地からみた関数プログラムの「標準形」となりうる可能性が示された., 07780227
    研究期間 1995年 - 1995年
  • 記号処理言語の新しい評価機構の関する研究
    岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 東京大学, 奨励研究(A), Improving Valueとは,「少しづつ(ある判断基準からみて)改良されていく値の系列」を表現するデータ構造であり,枝苅りに代表される探索問題において不要な探索を回避するのに役立つことが知られている.本研究では,関数型言語をはじめとする「記号処理言語」に関して,Improving Valueを一般化したデータ構造に基づく新たな評価機構の可能性について考察し,以下のような結果を得た. ・探索問題だけではなく,無限リストの長さを扱ったり繰り返し計算をおこなうような場面でImproving Valueが有効であることが判明した.ただし,関数型言語における参照透明性などの「良い性質」をいかに保存してImproving Valueを言語に採り入れるか,という問題点があることもわかった. ・評価機構としては従来のstrictな評価だけでは不十分で,強strict(従来のstrictに相当する)と弱strictという二段階の評価機構が必要であることが判明した. ・本研究費補助金によって購入した計算機を用いて,G-machineと呼ばれる関数型言語の翻訳系を,Inproving Valueを扱うことができるように拡張した. ・Improving Valueによる利点を享受するするためには,プログラムに対する静的な変換(前処理)をおこなうことも重要である.本研究では,構成的手法を用いた関数プログラム変換が実行効率の向上に広く貢献できることを示した., 06780235
    研究期間 1994年 - 1994年
  • 高機能高品質ソフトウエア構成法の研究
    中田 育男; 岩崎 英哉; 湯浅 太一; 斎藤 信男
    日本学術振興会, 科学研究費助成事業, 筑波大学, 重点領域研究, 本重点領域研究のA01班は、高機能高品質ソフトウェアは如何にあるべきか、如何に作るべきかを討論、検討するのを目的としている。班の研究集会は9月4〜5日、3月5〜6日の2回を開催し、出席者はそれぞれ11名、9名であった。 岩崎のグループは、高機能高品質プログラムの構成法についてUti Lispを例に考察した。その結果、高機能高品質ソフトウェアを構成する要因として、「ソフトウェアの核部分に一貫した設計思想と十分な機能を持たせて、それをユーザに公開することが重要である」との知見が得られた。Uti Lispの例でいえば自動記憶管理をもつような言語処理系が背後にひかえることにより、信頼性が高くなり、システムの品質も向上した。 斎藤のグループは、ソフトウェアのさまざまな構成要素にパラメタを与えられるように実現し、それをもとにさまざまな要求に応じられるようにすることを目標とし、ソフトウェア構成方法としてはオブジェクト指向構成方法がよいという結論を得た。 中田のグループは、コンパイラ生成系を改良したり、コンパイラ生成系の技術を他のソフトウェアに適用することによって、より高機能なソフトウェアや、より高品質なソフトウェアを、より機械的に構成する方法を研究した。具体的には、拡張1パス型属性交法、GUIのための時相属性交法などを開発した。, 04219103
    研究期間 1992年 - 1992年
  • 関数プログラムの並列実行に関する研究
    武市 正人; 金子 敬一; 岩崎 英哉
    日本学術振興会, 科学研究費助成事業, 東京大学, 一般研究(C), 本研究は、関数プログラミングの方法論を支援する並列実行システムの構築に関して基礎的な問題の解決法を追究したものである。関数プログラムの実行システムの実現については最近のハ-ドウェア技術の進歩による部分も大きいが、一般の計算機上で実現した関数プログラムの実行系は手続き型のものに比べて効率が悪いことは事実である。また、逐次計算機で関数プログラムを実行する際には本質的な問題があることも知られている。本研究では関数プログラムの並列実行を対象としてこの問題の解決法を探究した。関数プログラミングの方法論を実践する上では(複数個の処理装置による)並列実行システムが重要な役割を果たすものと考えられるからである。研究を進めるにあたっては、関数プログラミングの方法論を確立するための基礎的な研究の過程として、一般的なハ-ドウェアを用いて実験的な処理系を実現し、成果をただちに方法論の研究に活用することを考慮した。 第1段階として、逐次実行における遅延評価の問題点を並列実行によって解決する方法を考察した。この研究成果は関数プログラムの並列実行に関して物理的なプロセッサの割当てやプロセッサの結合方式を抽象したものであるが、共有メモリ型マルチプロセッサシステムに直ちに移行することのできるものである。第2段階として、複数個のプロセッサからなるネットワ-ク分散型のマルチプロセッサによる関数プログラムの並列実行系を設計・作成した。ここでは、遅延評価に基づく関数プログラミングに特徴的なストリ-ムを用いるプロセスネットワ-クのモデルに着目して、これを分散並列実行系で実現する方式を考案し、複数個の処理装置が通信路で結合された粗結合マルチプロセッサシステム上に関数プログラムの分散並列実行システムを構築し、その有効性を確認した。, 01550278
    研究期間 1989年 - 1990年