42 件中 1 - 42 件目
| 年度 Year |
論文題目名 Title of the articles |
共著区分 Collaboration Classification |
NeoCILIUS 請求番号／資料ID Request No |
|---|---|---|---|
| 掲載誌名 Journal name，出版機関名 Publishing organization，巻／号 Vol./no.，頁数 Page nos.，発行年月（日） Date | |||
| 2023 | Reversible computing from a programming language perspective | 共著 | |
| Theoretical Computer Science ， Elsevier ， 953 ， 1-29 ， 2023/04/10 | |||
|
概要（Abstract）
Software plays a central role in all aspects of reversible computing systems, and a variety of reversible programming languages have been developed. This presentation highlights the principles and main ideas of reversible computing viewed from a programming language perspective with a focus on clean reversible languages. They are the building material for software that can reap the benefits of reversible hardware and interesting in their own right. |
|||
|
備考（Remarks） https://doi.org/10.1016/j.tcs.2022.06.010 |
|||
| 2022 | Reversible Programming: A Case Study of Two String-Matching Algorithms | 共著 | |
| Electronic Proceedings in Theoretical Computer Science ， Open Publishing Association ， 373 ， 1-13 ， 2022/11/22 | |||
|
概要（Abstract） String matching is a fundamental problem in algorithm. This study examines the development and construction of two reversible string-matching algorithms: a naive string-matching algorithm and the Rabin-Karp algorithm. The algorithms are used to introduce reversible computing concepts, beginning from basic reversible programming techniques to more advanced considerations about the injectivization of the polynomial hash-update function employed by the Rabin-Karp algorithm. The results are two clean input-preserving reversible algorithms that require no additional space and have the same asymptotic time complexity as their classic irreversible originals. This study aims to contribute to the body of reversible algorithms and to the discipline of reversible programming. |
|||
|
備考（Remarks） http://dx.doi.org/10.4204/EPTCS.373.1 |
|||
| 2022 | Making Programs Reversible with Minimal Extra Data | 共著 | |
| New Generation Computing ， Springer ， 40 ， 467–480 ， 2022/07/04 | |||
|
概要（Abstract） Reversible computing is an unconventional computing paradigm that comes with specific challenges. One of the important questions is the existence of reversible programs with minimal extra output (garbage data). To answer this question for programs that implement partial functions over countable domains, we introduce an order on infinite garbage sets and a notion of minimality. To this end, we present two methods for functions specified by decidable and semi-decidable predicates. Both methods are universal, which means they work for all programs specified by the predicates. They cover Bennett’s classic input-erasing reversible computation of injective functions. Hence, any program written in a Turing-complete programming language can be implemented with g-minimal garbage in an r-Turing-complete reversible programming language. This generality comes at the cost of a considerable runtime due to the generate-and-test approach. |
|||
|
備考（Remarks） https://link.springer.com/article/10.1007/s00354-022-00169-z |
|||
| 2022 | From Reversible Programming Languages to Reversible Metalanguages | 共著 | |
| Theoretical Computer Science ， Elsevier ， Vol.920 ， pp. 46-63 ， 2022/06/12 | |||
|
概要（Abstract） During the past decade reversible programming languages have been formalized using various established semantics frameworks. However, these semantics fail to effectively specify the distinct properties of reversible languages at the metalevel, even including the central question of whether the defined language is reversible. In this paper, we build a metalanguage foundation for reversible languages from categorical principles, based on the category of sets and partial injective functions. We exemplify our approach by a step-by-step development of the full semantics of an r-Turing complete reversible while-language with recursive procedures. The use of the metalanguage leads to a formalization of the reversible semantics. A language defined in the metalanguage is guaranteed to have reversibility and inverse semantics. Also, program inverters for this language are obtained for free. We further discuss applications and directions for reversible semantics. |
|||
|
備考（Remarks）
https://doi.org/10.1016/j.tcs.2022.02.024 |
|||
| 2021 | 素朴な方法とRabin-Karp法による可逆文字列照合アルゴリズム | 共著 | |
| 南山大学紀要アカデミア理工学編 ， 南山大学 ， 22 ， pp. 124-132 ， 2022/03 | |||
|
概要（Abstract） 可逆性を有効に活用した計算システムでは，アルゴリズムも可逆であることが望ましいことが少なくない．本稿では素朴な方法と Rabin と Karp による文字列照合アルゴリズムの可逆版をそれぞれ作成し，時間計算量，空間計算量，及びゴミの量の解析を行う．可逆アルゴリズムは全ステップが単射でなければならない．我々は Rabin–Karp アルゴリズムで用いられるハッシュ値を更新する写像が単射であることを示す．素朴な方法の可逆版は（非可逆である）素朴な方法と時間計算量が同じであるものを作成した．可逆なRabin–Karp アルゴリズムは，前処理と後処理を除いた計算の時間計算量が非可逆なものと同じものを作成した．両者とも，空間計算量は対応する非可逆アルゴリズムと同じであり，ゴミは入力のみである．提案した可逆アルゴリズムは可逆プログラミング言語 Janus を用いて実装して動作を確認した． |
|||
|
備考（Remarks） http://doi.org/10.15119/00003946 |
|||
| 2020 | Complete Transition Diagrams of Generic Hamiltonian Flows with a Few Heteroclinic Orbits | 共著 | |
| Discrete Mathematics, Algorithms and Applications ， World Scientific ， Vol. 13, No. 02 ， 2150023 ， 2020/09 | |||
|
概要（Abstract） We study the transition graph of generic Hamiltonian surface flows, whose vertices are the topological equivalence classes of generic Hamiltonian surface flows and whose edges are the generic transitions. Using the transition graph, we can describe time evaluations of generic Hamiltonian surface flows (e.g. fluid phenomena) as walks on the graph. We propose a method for constructing the complete transition graph of all generic Hamiltonian flows. In fact, we construct two complete transition graphs of Hamiltonian surface flows having three and four genus elements. Moreover, we demonstrate that a lower bound on the transition distance between two Hamiltonian surface flows with any number of genus elements can be calculated by solving an integer programming problem using vector representations of Hamiltonian surface flows. |
|||
|
備考（Remarks） https://doi.org/10.1142/S1793830921500233 |
|||
| 2020 | Reversible Programs Have Reversible Semantics | 共著 | |
| In: Sekerinski E. et al. (eds) Formal Methods. FM 2019 International Workshops (FM 2019), Lecture Notes in Computer Science ， Springer-Verlag ， Vol.12233 ， pp. 413–427 ， 2020/08/10 | |||
|
概要（Abstract） During the past decade, reversible programming languages have been formalized using various established semantic frameworks. However, these semantics fail to effectively specify the distinct properties of reversible languages at the metalevel, and even neglect the central question of whether the defined language is reversible. In this paper, we build on a metalanguage foundation for reversible languages based on the category of sets and partial injective functions. We exemplify our approach through step-by-step development of the full semantics of an r-Turing complete reversible while-language with recursive procedures. This yields a formalization of the semantics in which the reversibility of the language and its inverse semantics are immediate, as well as the inversion of programs written in the language. We further discuss applications and future research directions for reversible semantics. |
|||
|
備考（Remarks） https://doi.org/10.1007/978-3-030-54997-8_26 |
|||
| 2019 | Analyzing Trade-offs in Reversible Linear and Binary Search Algorithms | 共著 | |
| Proceedings of the Third Workshop on Software Foundations for Data Interoperability (SFDI2019+), October 28, 2019, Fukuoka, Japan ， pp.1-5 ， 2019/10/23 | |||
|
概要（Abstract） Reversible algorithms are algorithms in which each step represents a partial injective function; they are useful for performance optimization in reversible systems. In this study, using Janus, a reversible imperative high-level programming language, we have developed reversible linear and binary search algorithms. We have analyzed the non-trivial space-time trade-offs between them, focusing on the memory usage disregarding original inputs and outputs, the size of the output garbage disregarding the original inputs, and the maximum amount of traversal of the input. The programs in this study can easily be adapted to other reversible programming languages. Our analysis reveals that the change of the output data and/or the data structure affects the design of efficient reversible algorithms. For example, the number of input data traversals depends on whether the search has succeeded or failed, while it expectedly never changes in corresponding irreversible linear and binary searches. Our observations indicate the importance of the selection of data structures and what is regarded as the output with the aim of the reversible algorithm design. |
|||
|
備考（Remarks）
https://arxiv.org/abs/1911.05900 |
|||
| 2019 | Constructing a Binary Tree from its Traversals by Reversible Recursion and Iteration | 共著 | |
| Information Processing Letters ， Elsevier ， 147 ， 32-37 ， 2019/07 | |||
|
概要（Abstract） We cast two algorithms generating the inorder and preorder traversals of a binary tree in the context of reversible computing nearly three decades after they were first examined in the light of program inversion. The reversible traversals directly define the inverse algorithms that reconstruct the tree. They have the same linear time and space requirements as the traversals. A while-language is extended with reversible recursion. |
|||
|
備考（Remarks） https://doi.org/10.1016/j.ipl.2019.03.002 |
|||
| 2018 | 多重連結領域上の安定非圧縮流のプリミティブな局所構造変換 | 共著 | |
| 電子情報通信学会和文論文誌D ， 電子情報通信学会 ， Vol.J102-D, No.3 ， 235-238 ， 2019/03/01 | |||
|
概要（Abstract） 局所構造変換を繰り返し適用して，一般に観測される多重連結領域上の非圧縮流の全トポロジーを構成できることを示した．3種類の初期大域構造に対して，7種類の局所構造を置換するアプローチを取った． |
|||
|
備考（Remarks） http://doi.org/10.14923/transinfj.2018JDL8021 |
|||
| 2018 | 二分木の辞書順のランク計算の効率的なクリーン可逆シミュレーション | 共著 | |
| 電子情報通信学会和文論文誌D ， 電子情報通信学会 ， Vol.J102-D, No.3 ， pp. 130-140 ， 2019/03/01 | |||
|
概要（Abstract） 可逆システム上で非可逆プログラムの可逆シミュレーションを実現するとき，既知の一般解法を用いると，元の入出力の走査回数と，元の入出力用以外のメモリ使用量が増え，元の出力以外を出力してクリーンでなくなってしまうという問題が起こる．しかし，非可逆なアルゴリズムに対して，経験と勘を元に個別の非可逆プログラムの効率的なクリーン可逆シミュレーションが実現されてきている．本稿では，可逆計算システムで用いる可逆アルゴリズムとして，二分木の列挙，二分木の辞書順のランク計算，および辞書順における次の二分木の生成の効率的なクリーン可逆シミュレーションの構築をする．これらは基礎的な可逆アルゴリズムであるので，他の可逆アルゴリズムの一部として使用されたり，可逆アルゴリズムの構築法が利用されたりすることが期待される．また，二分木のランク計算に関する効率的な可逆プログラムの整備を進めることで類似するランク計算やさらには現時点では困難な一般の効率的可逆シミュレーションの自動導出が可能になることが期待される．本稿の可逆プログラムは全てオンラインインタプリタで実行して振る舞いを確かめることが可能である． |
|||
|
備考（Remarks） 10.14923/transinfj.2018PDP0021 |
|||
| 2018 | 可逆プログラミング言語R-WHILEの可逆チューリング完全性 | 共著 | |
| 電子情報通信学会和文論文誌D ， 電子情報通信学会 ， J101-D, No.9 ， pp. 1372-1375 ， 2018/09/01 | |||
|
概要（Abstract） 任意の可逆プログラミング言語のプログラムで計算できるものが，可逆なR-WHILEプログラムによって計算できることを示す． |
|||
|
備考（Remarks） DOI: 10.14923/transinfj.2018JDL8008 |
|||
| 2018 | ハミルトン曲面流に対応する流れの向きを考慮した極大語の列挙アルゴリズム | 共著 | |
| 電子情報通信学会論文誌 D ， 電子情報通信学会 ， Vol.J101-D, No.8 ， pp. 1220-1222 ， 2018/08/01 | |||
|
概要（Abstract）
ハミルトン曲面流を表す流れの向きを考慮した極大語の表現法，任意の長さの極大語をもれなく重複無く列挙するアルゴリズム，及びステートチャートによる極大語の生成方法の簡潔な表現を示した．本手法で向きを考慮した流れの総数を見積もれる． |
|||
|
備考（Remarks） http://search.ieice.org/bin/summary.php?id=j101-d_8_1220&category=D&year=2018&lang=J&abst= |
|||
| 2017 | Clean Reversible Simulation of Ranking Binary Trees | 共著 | |
| Reversibility and Universality ， Springer-Verlag ， Vol.30 ， pp. 243-267 ， 2018/03 | |||
|
概要（Abstract） We propose clean reversible simulations of ranking binary trees and unranking as reversible algorithms for reversible computing systems, which are useful for enumerating and randomly generating binary trees. Algorithms for ranking binary trees and their inverses have been studied since the 1970s. Each of these algorithms can be converted into a reversible simulation by saving all data and control information otherwise lost, and each pair of ranking and unranking reversible pro- grams can be combined to realize a clean reversible simulation by using the Bennett method. However, such a clean reversible simulation requires multiple traversal of the given data and/or intermediate data as well as additional storage proportional to the length of the computation. We show that for Knott's ranking and unranking algorithms, additional storage usage can be reduced by using the proper assertions of reversible loops in embedded reversible simulations. We also show a clean reversible simulation that involves only one traversal. The running time and memory usage of the proposed clean reversible simulations are asymptotically equivalent to those of the original programs by Knott with intermediate garbage of constant size. In general, the derivation strategy of efficient reversible programs from irreversible ones has not yet been established, and this study can be seen as one of the case studies. All the reversible programs presented in this paper can be run on an interpreter of the reversible programming language Janus. |
|||
|
備考（Remarks） https://doi.org/10.1007/978-3-319-73216-9_11 |
|||
| 2017 | 可逆ビンソート | 単著 | |
| 電子情報通信学会論文誌 D ， 電子情報通信学会 ， Vol.J101-D, No.5 ， pp. 791-793 ， 2018/01/19 | |||
|
概要（Abstract） 非比較ソートであるビンソートの可逆シミュレーションを示し，効率的な非可逆ビンソートに対して時間/空間計算量が共に線形で出力ゴミが入力データと漸近的に同じ大きさの置換を表す配列になることを示す． |
|||
|
備考（Remarks）
DOI: 10.14923/transinfj.2017JDL8021 |
|||
| 2017 | 可逆プログラムのための償却定数時間かつ定数ゴミ使用量のメモ化 | 単著 | |
| 電子情報通信学会和文論文誌D ， 電子情報通信学会 ， Vol.J100-D, No.10 ， pp. 895-896 ， 2017/10/01 | |||
|
概要（Abstract） メモ化アルゴリズムの可逆版を提案する．本手法により得られるクリーン可逆プログラムは，可逆二進計数器を抽象解釈とする．単射な隣接2項間漸化式で表される任意の数列に対して償却定数時間で定数ゴミ使用量の可逆プログラムを得る方法を示す． |
|||
|
備考（Remarks） https://search.ieice.org/bin/summary.php?id=j100-d_10_895 |
|||
| 2017 | ハミルトン曲面流に対応する語の列挙アルゴリズム | 共著 | |
| 電子情報通信学会和文論文誌D ， 電子情報通信学会 ， Vol.J100-D, No.10 ， pp. 892-894 ， 2017/10/01 | |||
|
概要（Abstract）
ハミルトン曲面流に関する極大語の自然な分類が有限個であることを示し，その各分類の下での全ての極大語の列挙アルゴリズムの構成法を明らかにした．また，各分類において極大語の総数を求める方法を形式言語理論を応用して示した． |
|||
|
備考（Remarks） http://search.ieice.org/bin/summary.php?id=j100-d_10_892&category=D&year=2017&lang=J&abst= |
|||
| 2017 | A Minimalist's Reversible While Language | 共著 | |
| IEICE on Information and Systems ， Institute of Electronics, Information and Communication Engineers ， Vol.E100-D/No.5 ， pp. 1026-1034 ， 2017/05/01 | |||
|
概要（Abstract） The paper presents a small reversible language R-CORE, a structured imperative programming language with symbolic tree-structured data (S-expressions). The language is reduced to the core of a reversible language, with a single command for reversibly updating the store, a single reversible control-flow operator, a limited number of variables, and data with a single atom and a single constructor. Despite its extreme simplicity, the language is reversibly universal, which means that it is as powerful as any reversible language can be, while it is linear-time self-interpretable, and it allows reversible programming with dynamic data structures. The four-line program inverter for R-CORE is among the shortest existing program inverters, which demonstrates the conciseness of the language. The translator to R-CORE, which is used to show the formal properties of the language, is clean and modular, and it may serve as a model for related reversible translation problems. The goal is to provide a language that is sufficiently concise for theoretical investigations. Owing to its simplicity, the language may also be used for educational purposes. |
|||
|
備考（Remarks） http://doi.org/10.1587/transinf.2016EDP7274 |
|||
| 2016 | A Linear-Time Self-Interpreter of a Reversible Imperative Language | 共著 | |
| Computer Software ， Japan Society for Software Science and Technology (JSSST) ， 3 ， pp. 108–128 ， 2016/08/10 | |||
|
概要（Abstract） A linear-time reversible self-interpreter in an r-Turing complete reversible imperative language is presented. The proposed imperative language has reversible structured control flow operators and symbolic tree-structured data (S-expressions). The latter data structures are dynamically allocated and enable reversible simulation of programs of arbitrary size and space consumption. As self-interpreters are used to show a number of fundamental properties in classic computability and complexity theory, the present study of an efficient reversible self-interpreter is intended as a basis for future work on reversible computability and complexity theory as well as programming language theory for reversible computing. Although the proposed reversible interpreter consumes superlinear space, the restriction of the number of variables in the source language leads to linear-time reversible simulation. |
|||
|
備考（Remarks）
http://doi.org/10.11309/jssst.33.3_108 |
|||
| 2015 | Fundamentals of reversible flowchart languages | 共著 | doi:10.1016/j.tcs.2015.07.046 |
| Theoretical Computer Science ， Elsevier ， 611 ， 87-115 ， 2016/01/18 | |||
|
概要（Abstract）
This paper presents the fundamentals of reversible flowcharts. Reversible flowcharts are intended to naturally represent the structure and control flow of reversible (imperative) programming languages in a simple computation model in the same way classical flowcharts do for conventional languages. Although reversible flowcharts are superficially similar to classical flowcharts, there are crucial differences: atomic steps are limited to locally invertible operations, and join points require an explicit orthogonalizing conditional expression. |
|||
|
備考（Remarks） http://dx.doi.org/10.1016/j.tcs.2015.07.046 |
|||
| 2015 | Programming Techniques for Reversible Comparison Sorts | 共著 | 10.1007/978-3-319-26529-2_22 |
| Lecture Notes in Computer Science ， Springer-Verlag ， 9458 ， pp. 407-426 ， 2015/12/09 | |||
|
概要（Abstract）
A common approach to reversible programming is to reversibly simulate an irreversible program with the desired functionality, which in general puts additional pressure on the computational resources (time, space.) If the same running time is required, ensuring a minimal space overhead is a significant programming challenge. |
|||
|
備考（Remarks） https://doi.org/10.1007/978-3-319-26529-2_22 |
|||
| 2014 | Designing Garbage-Free Reversible Implementations of the Integer Cosine Transform | 共著 | |
| ACM Journal on Emerging Technologies in Computing Systems ， 11 ， pp. 1-15 ， 2014/11 | |||
|
概要（Abstract） Discrete linear transformations are important tools in information processing. Many such transforms are injective and therefore prime candidates for a physically reversible implementation into hardware. We present here reversible integer cosine transformations on n input integers. The resulting reversible circuit is able to perform both the forward transform and the inverse transform. The detailed structure of such a reversible design strongly depends on the odd prime factors of the determinant of the transform: whether those are of the form 2k ± 1 or of the form 2k ± 2l ± 1 or neither of these forms. |
|||
|
備考（Remarks） |
|||
| 2014 | 可逆プログラミング言語の引数渡し機構の拡張 | 共著 | |
| 情報処理学会論文誌：プログラミング ， 情報処理学会 ， 7 ， 21-36 ， 2014/08 | |||
|
概要（Abstract） 本稿では,可逆プログラミング言語Janusの引数渡し機構を拡張して,その拡張言語が可逆であることを示す.参照渡しのモデル化には,同一の参照を持つかもしれない複数の変数名が同じ記憶場所を指せるメモリモデルが必要である.これは既存のJanusで用いられていた状態モデルでは直接には扱うことができない.この問題を解決するために,我々は,環境・記憶域モデルを導入して意味論を改良した.この結果,プロシージャの実引数には,局所変数や局所配列変数だけでなく大域変数や添字付き配列変数の参照,および同一の参照を持つ複数の構文対象も渡せるようになった.拡張言語が可逆であることの保証には,環境と記憶域の更新が可逆であることの保証が必要である.これらの更新は,制限された可逆操作のみ用いて実現されることで,可逆であることが保証される.我々は,拡張言語がほかにも既存のJanusの良い性質を保っていることを示す.すなわち,任意の文やプロシージャ呼び出しの逆実行ができること,および任意の文に対して逆文が存在してそれを求めるプログラム逆変換器が構成できることを示す.さらに,我々は,プログラミング言語を可逆にするために課されていた代入の構文上の制限を緩和する.このことが原因で起こる記憶域の不正な更新は,大域のプログラム解析をしなくても,効率的に検知することができる. |
|||
|
備考（Remarks）
http://id.nii.ac.jp/1001/00102871/ |
|||
| 2012 | Minimizing Garbage Size by Generating Reversible Simulations | 共著 | |
| Reversibility, cellular automata, and unconventional computation. Proceedings. ， IEEE Computer Society ， 379–387 ， 2012/12/05 | |||
|
概要（Abstract） Reversible simulations can realize any irreversible computation on any r-Turing complete reversible computation model at the expense of additional garbage output. The problem of minimizing the garbage size is an important issue in reversible simulations. We discuss the notion of the minimal garbage size of reversible simulations. Then, we propose a three-stage reversible simulation for minimizing garbage size, the first stage generates specialized irreversible programs, the second translates them into reversible simulations, and the third performs reversible simulation using the generated reversible programs. Two case studies on sorting algorithms suggest that the proposed method generates solutions with minimal garbage size. |
|||
|
備考（Remarks） http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6424599&isnumber=6424528 |
|||
| 2011 | Optimizing Input-Erasing Clean Reversible Simulation for Injective Functions | 共著 | |
| Multiple-Valued Logic and Soft Computing ， Old City Publishing ， Vol.18/no.1 ， 5–24 ， 2012/01 | |||
|
概要（Abstract） Bennett showed that a clean reversible simulation of injective programs is possible without returning the input of a program as additional output. His method involves two computation and two uncomputation phases. This paper proposes an optimization of Bennett’s simulation that requires only half of the computation and uncomputation steps for a class of injective programs. A practical consequence is that the reversible simulation runs twice as fast as Bennett’s simulation. The proposed method is demonstrated by developing lossless encoders and decoders for run-length encoding and range coding. The range-coding program is further optimized by conserving the model over the text-generation phase. This paper may thus provide a new view on developing efficient reversible simulations for a certain class of injective functions. |
|||
|
備考（Remarks） http://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-18-number-1-2012/mvlsc-18-1-p-5-24/ |
|||
| 2011 | Towards a Reversible Functional Language | 共著 | |
| Lecture Notes in Computer Science ， Springer-Verlag ， Vol. 7165 ， 14–29 ， 2012 | |||
|
概要（Abstract）
We identify concepts of reversibility for a functional language |
|||
|
備考（Remarks） |
|||
| 2011 | Static Task Scheduling Algorithms Based on Greedy Heuristics for Battery-Powered DVS Systems | 共著 | |
| IEICE Trans. on Information and Systems ， The Institute of Electronics, Information and Communication Engineers ， E93-D ， 2737-2746 ， 2010/10 | |||
|
概要（Abstract） We identify concepts of reversibility for a functional language by means of a set of semantic rules with specific properties. These properties include injectivity along with local backward determinism, an important operational property for an efficient reversible language. We define a concise reversible first-order functional language in which access to the backward semantics is provided to the programmer by inverse function calls. Reversibility guarantees that in this language a backward run (inverse interpretation) is as fast as the corresponding forward run itself. By adopting a symmetric first-match policy for case expressions, we can write overlapping patterns in case branches, as is customary in ordinary functional languages, and also in leaf expressions, unlike existing inverse interpreter methods, which enables concise programs. In patterns, the use of a duplication/equality operator also simplifies inverse computation and program inversion. We discuss the advantages of a reversible functional language using example programs, including run-length encoding. Program inversion is seen to be as lightweight as for imperative reversible languages and realized by recursive descent. Finally, we show that the proposed language is r-Turing complete. |
|||
|
備考（Remarks） |
|||
| 2009 | Reversible Computation and Reversible Programming Languages | 単著 | |
| Electronic Notes in Theoretical Computer Science ， Elsevier ， 253(6) ， 71-81 ， 2010/03 | |||
|
概要（Abstract） |
|||
|
備考（Remarks）
以下における招待講演を改訂したもの． |
|||
| 2009 | Practical Energy-Aware Scheduling for Real-Time Multiprocessor Systems | 共著 | |
| 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications ， IEEE Press ， 2009/08 | |||
|
概要（Abstract） Energy-aware real-time multiprocessor scheduling has been studied extensively so far. However, some of the constraints associated with the practical DVS applications have been ignored for simplicity. These constraints include discrete speed, idle power, inefficient speed, and application-specific power characteristics etc. This work targets energy-aware scheduling of periodic real-time tasks on the DVS-equipped multiprocessor systems with practical constraints. An adaptive minimal bound first-fit (AMBFF) algorithm with consideration of these realistic constraints is proposed for both dynamic-priority and fixed-priority multiprocessor scheduling. Simulation results on three commercial processor models show that our algorithm can save significantly more energy than existing algorithms. |
|||
|
備考（Remarks） https://doi.org/10.1109/RTCSA.2009.47 |
|||
| 2009 | Heuristics for Static Voltage Scheduling Algorithms on Battery-Powered DVS Systems | 未設定 | |
| 2009 International Conference on Embedded Software and Systems ， IEEE Computer Society ， 265-272 ， 2009/05 | |||
|
概要（Abstract） The principles for good design of battery-aware voltage scheduling algorithms for both aperiodic and periodic task sets on dynamic voltage scaling (DVS) systems are presented. The proposed algorithms are based on greedy heuristics suggested by several battery characteristics and Lagrange multipliers. To construct the proposed algorithms, we use the battery characteristics in the early stage of scheduling more properly. As a consequence, the proposed algorithms show superior results on synthetic examples of periodic and aperiodic tasks from the task sets which are excerpted from the comparative work, on uniprocessor platforms. Especially, for some large task sets, the proposed algorithms enable previously unschedulable task sets due to battery exhaustion to be schedulable. |
|||
|
備考（Remarks） https://doi.org/10.1109/ICESS.2009.19 |
|||
| 2009 | Analyzing and optimizing energy efficiency of algorithms on DVS systems: A first step towards algorithmic energy minimization | 共著 | |
| Asia and South Pacific Design Automation Conference (ASP-DAC) ， IEEE Press ， 727–732 ， 2009/01 | |||
|
概要（Abstract） The energy efficiency at the algorithmic level on DVS systems and its analysis and optimization methods are presented. Given a problem the most energy efficient algorithm is not uniquely determined but dependent on multiple factors, including intratask dynamic voltage scaling (IntraDVS) policies, the size of intermediate data structure, and the size of inputs. We show that at the algorithmic level principles behind energy optimization and performance optimization are not identical. We propose a metric for evaluating optimal energy efficiency of static voltage scaling (SVS) and a few new effective IntraDVS policies employing data flow information. Experimental results on sorting algorithms show the existence of several tradeoffs in terms of energy consumption. Transforming algorithms by employing problem specific knowledge and data flow information successfully improves their energy efficiency. |
|||
|
備考（Remarks） https://doi.org/10.1109/ASPDAC.2009.4796566 |
|||
| 2008 | 動的電圧制御システムにおける評価戦略選択に基づく高効率消費エネルギー関数型プログラミング | 共著 | http://ci.nii.ac.jp/naid/110007970891 |
| 情報処理学会論文誌：トランザクション「プログラミング」 ， 情報処理学会 ， Vol.2, No.2(PRO41) ， 54-69 ， 2009/03 | |||
|
概要（Abstract） 動的電圧制御 （DVS: dynamic voltage scaling） は，プロセッサへの供給電圧とその動作周波数をプログラム実行時に変化させる技術であり，現在，多くの商用プロセッサに実装されている．本稿では，デッドラインなどの制約のあるリアルタイムシステムを対象に，DVS システムにおいて動的エネルギー消費のより少ないプログラムを開発する方法論の 1 つを提示する．DVS システムで実行されるプログラムに動的エネルギー消費の最適化が有効であるためには，残り予測実行時間の実行早期の正確な見積りを容易にすることが重要である．そのため，プログラムは何を計算するかに加えどう計算するかをうまく指定する必要がある．しかし，プログラム改変によるエネルギー消費の最適化はプログラムのモジュール性を著しく損なう．本稿では，プログラムから独立し，エネルギー消費の最適化戦略を開発する手法を提案する．提案手法により，エネルギー消費の最適化を行うときに元のプログラムの部分正当性が容易に保存され，元のプログラムおよびエネルギー消費の最適化を行うための評価戦略が独立してそれぞれモジュール性を有するようになった．遅延評価などのプログラミング言語の特徴や構成的アルゴリズム論における組化などを活用することにより半自動化が実現できたことが，本開発法の特徴の 1 つである．本稿では，整列，選択，文字列検索などの基本的なアルゴリズムに提案手法を適用する．また，電力モデルを備えた命令セットシミュレータ（ISS: instruction set simulator）において実験を行い，エネルギー消費がどれだけ最適化されたかを評価する．基本的なアルゴリズムにおいて，本稿のアプローチが有効であることから，複雑なアルゴリズムに対しても本手法が効果的であることが期待される． |
|||
|
備考（Remarks）
以下で発表したものを改訂したもの． |
|||
| 2008 | A Generalized Framework for Energy Savings in Real-Time Multiprocessor Systems | 共著 | |
| Proceedings of 2008 International SoC Design Conference ， IEEE ， 727-732 ， 2009/01 | |||
|
概要（Abstract） A generalized dynamic energy performance scaling (DEPS) framework is proposed for exploring application-specific energy-saving potential in multiprocessor systems. This software-centric framework takes advantage of possible power control mechanisms to trade off performance for energy savings. Three existing technologies, i.e., dynamic hardware resource configuration (DHRC), dynamic voltage frequency scaling (DVFS), and dynamic power management (DPM), have been employed in this framework to achieve the maximal energy savings. The problem of determining the optimal task allocation and DEPS configurations is formulated as an integer linear programming (ILP) problem. Several practical issues such as how to reduce measurement and computation time and how to reduce the configuration overhead are also addressed. The effectiveness of DEPS is validated through a case study. |
|||
|
備考（Remarks）
DOI: 10.1109/SOCDC.2008.4815570 |
|||
| 2008 | Reversible Flowchart Languages and the Structured Reversible Program Theorem | 共著 | |
| Automata, Languages and Programming ， Springer ， LNCS 5126 ， 258-270 ， 2008/08 | |||
|
概要（Abstract） Many irreversible computation models have reversible counterparts, but these are poorly understood at present. We introduce reversible flowcharts with an assertion operator and show that any reversible flowchart can be simulated by a structured reversible flowchart using only three control flow operators. Reversible flowcharts are r-Turing-complete, meaning that they can simulate reversible Turing machines without garbage data. We also demonstrate the injectivization of classical flowcharts into reversible flowcharts. The reversible flowchart computation model provides a theoretical justification for low-level machine code for reversible microprocessors as well as high-level block structured reversible languages. We give examples for both such languages and illustrate them with a lossless encoder for permutations given by Dijkstra. |
|||
|
備考（Remarks） |
|||
| 2008 | Principles of a reversible programming languages | 未設定 | |
| CF '08: Proceedings of the 5th conference on Computing frontiers ， ACM Press ， 43–54 ， 2008/05 | |||
|
概要（Abstract） The principles of reversible programming languages are explicated and illustrated with reference to the design of a high-level imperative language, Janus. The fundamental properties for such languages include backward as well as forward determinism and reversible updates of data. The unique design features of the language include explicit post-condition assertions, direct access to an inverse semantics and the possibility of clean ({\ie}, garbage-free) computation of injective functions. We suggest the clean simulation of reversible Turing machines as a criterion for computing strength of reversible languages, and demonstrate this for Janus. We show the practicality of the language by implementation of a reversible fast Fourier transform. Our results indicate that the reversible programming paradigm has fundamental properties that are relevant to many different areas of computer science. |
|||
|
備考（Remarks） https://dl.acm.org/doi/10.1145/1366230.1366239 |
|||
| 2007 | Reversible Machine Code and Its Abstract Processor Architecture | 共著 | |
| Computer Science -- Theory and Applications ， Springer ， LNCS 4649 ， 56-69 ， 2007/09 | |||
|
概要（Abstract） A reversible abstract machine architecture and its reversible machine code are presented and formalized. For machine code to be reversible, both the underlying control logic and each instruction must be reversible. A general class of machine instruction sets was proven to be reversible, building on our concept of reversible updates. The presentation is abstract and can serve as a guideline for a family of reversible processor designs. By example, we illustrate programming principles for the abstract machine architecture formalized in this paper. |
|||
|
備考（Remarks）
以下で発表したものを改訂したもの． |
|||
| 2006 | Program Optimizations and Transformations in Calculation Form | 共著 | |
| Generative and Transformational Techniques in Software Engineering ， Springer ， LNCS 4143 ， 144-168 ， 2006/11 | |||
|
概要（Abstract） The world of program optimization and transformation takes on a new fascination when viewed through the lens of program calculation. Unlike the traditional fold/unfold approach to program transformation on arbitrary programs, the calculational approach imposes restrictions on program structures, resulting in some suitable calculational forms such as homomorphisms and mutumorphisms that enjoy a collection of generic algebraic laws for program manipulation. In this tutorial, we will explain the basic idea of program calculation, demonstrate that many program optimizations and transformations, such as the optimization technique known as loop fusion and the parallelization transformation, can be concisely reformalized in calculational form, and show that program transformation in calculational forms is of higher modularity and more suitable for efficient implementation. |
|||
|
備考（Remarks）
以下を改訂したもの． |
|||
| 2004 | 決定論的2階パターンとプログラム変換への応用 | 共著 | |
| コンピュータソフトウェア ， 日本ソフトウェア科学会 ， Vol. 21、No. 5 ， 71-76 ， 2004/09 | |||
|
概要（Abstract） 2階パターンと2階照合を用いると高度なプログラム変換を記述することができることが知られている．しかし，2階照合はNP困難であるため効率がよい実装が望めない．われわれは，2階パターンの形を制限することで，どのような項とも得られる最汎照合子が高々1つである決定論的なパターンのクラスを定め，またこの照合を得るための効率の良いアルゴリズムを開発した．本稿では，このような決定論的2階パターンのクラスを拡張し，また線形2階パターンが決定論的であるための必要十分条件を与える．このクラスのパターンを用いて幅広いプログラム変換を記述することが可能である． |
|||
|
備考（Remarks） https://doi.org/10.11309/jssst.21.403 |
|||
| 2004 | Deterministic Second-Order Patterns | 共著 | |
| Information Processing Letters ， Elsevier ， 89(6) ， 309-314 ， 2004/03 | |||
|
概要（Abstract） Second-order patterns, together with second-order matching, enable concise specification of program transformation, and have been implemented in several program transformation systems. However, second-order matching in general is nondeterministic, and the matching algorithm is so expensive that the matching is NP-complete. It is orthodox to impose constraints on the form of higher-order patterns so as to obtain the desirable matches satisfying certain properties such as decidability and finiteness. In the context of unification, Miller's higher-order patterns have a single most-general unifier. In this paper, we relax the restriction of his patterns without changing determinism in the context of matching instead of unification. As a consequence, our deterministic second-order patterns cover a wide class of useful patterns for program transformation. The time-complexity of our deterministic matching algorithm is linear in the size of a term for a fixed pattern. |
|||
|
備考（Remarks） https://doi.org/10.1016/j.ipl.2003.12.008 |
|||
| 2003 | Deterministic Higher-Order Patterns for Program Transformation | 共著 | |
| Logic Based Program Synthesis and Transformation ， Springer ， LNCS 3018 ， 128-142 ， 2004/08 | |||
|
概要（Abstract） Higher-order patterns, together with higher-order matching, enable concise specification of program transformation, and have been implemented in several program transformation systems. However,higher-order matching in general is nondeterministic, and the matching algorithm is so expensive that even second-order matching is NP-complete. It is orthodox to impose constraint on the form of patterns to obtain the desirable matches satisfying certain properties such as decidability and finiteness. In the context of unification, Miller’s higher-order patterns have a single most general unifier. We relax the restrictions in his patterns without changing determinism within the context of matching instead of unification. As a consequence, the new class of patterns covers a wide class of useful patterns for program transformation. The time-complexity of the matching algorithm is linear for the size of a term for a fixed pattern. |
|||
|
備考（Remarks）
以下を改訂したもの． |
|||
| 2002 | Yicho - A System for Programming Program Calculations | 共著 | |
| Mathematical Engineering Technical Reports ， the University of Tokyo ， 7 ， 1-17 ， 2002/06 | |||
|
概要（Abstract） |
|||
|
備考（Remarks） |
|||
| 2002 | 変換戦略の記述に基づくプログラムの自動生成システムの実装 | 共著 | |
| 情報処理学会論文誌：トランザクション「プログラミング」 ， 情報処理学会 ， Vol. 43 No. SIG3 ， 62-77 ， 2002/03 | |||
|
概要（Abstract）
プログラムの自動生成においては，変換規則の汎用性を高めるために，変換規則と変換規則の適用順序を制御することが重要である．変換規則と変換戦略を記述する理論的枠組みであるCCP（Calculation Carrying Program）についてはすでに報告しているが，筆者らの知る限りにおいては計算機上で稼動されたという報告はなく，CCPによる大きなプログラムの変換についての報告もない．本論文では，CCPの処理系を実装する方法を考察し，計算機上で実際に最大マーク付け問題のプログラムの自動生成について検討を行い，本システムの有効性を示す． |
|||
|
備考（Remarks）
最大マーク付け問題の効率的プログラムの自動生成（情報処理学会第36回プログラミング研究会）を改訂したもの |
|||
Page: [<<PREV] [1] [NEXT>>]
Copyright(C) 2010 Software Research Associates, Inc. All Rights Reserved.