金田の論文 年降順

From Matrix-Based to Dynamical Deep Learning: Synchronization and Energy

Kanada, Y. / 未出版, 2026 / 2026-01-20

Deep learning has historically developed around discrete, matrix-based representations that align naturally with GPU-oriented, globally synchronized computation. While this paradigm has enabled remarkable computational performance, the power required for large-scale training and inference has become a significant practical and societal constraint as model size and deployment scale continue to grow. In recent years, continuous-time and dynamical formulations such as Neural Ordinary Differential Equations, diffusion models, and state-space models have gained increasing attention. This paper argues that this representational shift has implications beyond modeling style. First, it challenges the implicit reliance on global synchronization inherent in matrix-centric computation, opening possibilities for more asynchronous or locally coordinated execution. Second, it suggests new opportunities for improving energy efficiency by reducing synchronization and data movement overhead. Third, this transition admits a limited but informative structural analogy with the historical development of quantum mechanics, in which matrix mechanics and wave mechanics emerged as distinct yet complementary representational frameworks. Without claiming mathematical equivalence, this analogy is proposed as a conceptual perspective for understanding an ongoing transition in the foundations of deep learning.

個人名やペンネームをプロンプトとして 生成 AI の「画才」をひきだす

Kanada, Y. / Nicograph 2024, 2024-11 / 2024-11-01

Image generation AI can produce images even when given invented or unrelated words that it hasn’t been specifically trained on. Using personal names or coined pen names functioning as artist names, I provided short prompts of about 2-3 words to Stable Diffusion XL to create painting-like images. The choice of pen name helps define the generated image’s character, giving personality to the artist name. Since Stable Diffusion allows for negative prompts, even greater image variety can be achieved. By adjusting random seeds to generate a wide range of images, I could select those where the AI’s “artistic talent” was particularly evident. The exhibition will focus on about ten especially interesting pieces, with others included for reference.

C. P. E. バッハと 18 世紀の鍵盤楽器，「平均律クラヴィーア」という誤訳 (未発表資料)

2024-10-01

Emergent Text-to-Image Generation Using Short Neologism Prompts and Negative Prompts

Kanada, Y. / 2024-06-01

Stable Diffusion (SD) や DALL·E のような text-to-image generation model によって，プロンプトとよばれるテキストから様々な種類の画像が生成できる．AI アーティストは好みの画像を生成するために長いプロンプトを使用することが多いが，このポスターでは SD と 1〜2 語の短いプロンプトを使用することにより，AI に創発させ，多様な絵画的な画像を生成する方法を提案する．このような試みをしているのは，AI は学習した画像情報から色・形などの表現とその裏にある原画像の作者の意図や動機などをひきだして生成画像に反映させているとかんがえ，AI 使用者が生成画像に遭遇し選びだすのが創造的な過程だとかんがえるからである．

1 個ずつことなる製品の連続生産をめざした design と製造の試み

Kanada, Y. / Design シンポジウム 2021, 2021-7 / 2021-07-16

(no English abstract)

螺旋3D印刷法とその照明器具への応用

金田 泰 / プラスチックス, 2019 年 3 月号, pp. 45-50 / 2019-03-07

Spiral (helical) 3D printing is a 3D printing method in which a single spiral winding of a filament can create a variety of shapes and apply fine textures and patterns to the surface. He describes what can be made by spiral 3D printing, its principles, how to make it, what kind of software to use, and the development and future of products other than products. (Google translation)

Complex Moiré Patterns Generated by Helical 3D Printing with Three Waves

Kanada, Y. / not yet published, 2018 / 2018-07-22

This poster proposes a method for generating fine asperity by helical 3D printing using three types of waves, especially for generating complex Moiré patterns. The printing process can be modulated by three types of sine waves while printing.

3D プリンタもプログラミングで ─ draw3dp (ちょっと変わったプログラミング教室 03)

Kanada, Y. / 情報処理, Vol. 58, No. 6, pp. 17–23, 2017-6 / 2017-04-22

The current mainstream 3D design and printing methods are versatile but not versatile, so other methods may be needed. In some cases, simply specifying the surface shape is not enough, and there are some shapes that cannot be printed well by the mainstream method. In such a case, a field-oriented object model that can specify the direction (printing direction) at each point on the model, a design method using a procedural program, and a printing method that is not limited to the horizontal direction are effective. Although these methods do not have the versatility of the mainstream methods, they are effective for the purpose for which they are suitable, for example, for the formation of hollow solids. The outline of this method and the library to use draw3dp are described in another paper, but this article introduces the background, related trends, and applications. (Google translation)

Method for Procedural 3D Printing Using a Python Library

Kanada, Y. / Journal of Information Processing, Vol. 24, No. 6, pp. 908–916, 2016-11 / 2016-11-17

When manufacturing or 3D-printing a product using a computer, a program that procedurally controls manufacturing machines or 3D printers is required. G-code is widely used for this purpose. G-code was developed for controlling subtractive manufacturing (cutting work), and designers have historically written programs in G-code, but, in recently developed environments, the designer describes a declarative model by using computer-aided design (CAD), and the computer converts it to a G-code program. However, because the process of additive manufacturing, of which FDM-type 3D-printing is a prominent example, is more intuitive than subtractive manufacturing, it is some- times advantageous for the designer to describe an abstract procedural program for this purpose. This paper therefore proposes a method for generating G-code by describing a Python program using a library for procedural 3D design and for printing by a 3D printer, and it presents use cases. Although shapes printable by the method are restricted, this method can eliminate layers and layer seams as well as support, which is necessary for conventional methods when an overhang exists, and it enables seamless and aesthetic printing.

Python ライブラリを使用した手続き的な 3D 印刷法 (Method for Procedural 3D Printing Using a Python Library)

Kanada, Y. / IPSJ Transactions on Programming, Vol. 9, No. 4, pp. 1–9, 2016-9 / 2016-08-03

When manufacturing or 3D-printing a product using a computer, a program that procedurally controls manufacturing machines or 3D printers is required. G-code is widely used for this purpose. G-code was developed for controlling subtractive manufacturing (cutting work), and designers have historically written programs in G-code, but, in recently developed environments, the designer describes a declarative model by using computer-aided design (CAD), and the computer converts it to a G-code program. However, because the process of additive manufacturing, of which FDM-type 3D-printing is a prominent example, is more intuitive than subtractive manufacturing, it is some- times advantageous for the designer to describe an abstract procedural program for this purpose. This paper therefore proposes a method for generating G-code by describing a Python program using a library for procedural 3D design and for printing by a 3D printer, and it presents use cases. Although shapes printable by the method are restricted, this method can eliminate layers and layer seams as well as support, which is necessary for conventional methods when an overhang exists, and it enables seamless and aesthetic printing.

Optimizing Neural-network Learning Rate by Using a Genetic Algorithm with Per-epoch Mutations

Kanada, Y. / 2016 International Joint Conference on Neural Networks (IJCNN 2016), July 2016 / 2016-07-27

Recently, performance of deep neural networks, especially convolutional neural networks (CNNs), has been drastically increased by elaborate network architectures, by new learning methods, and by GPU-based high-performance compu- tation. However, there are still several difficult problems concerning back propagation, which include scheduling of learning rate and controlling locality of search (i.e., avoidance of bad local minima). A learning method, called “learning-rate- optimizing genetic back-propagation” (LOG-BP), which com- bines back propagation with a genetic algorithm by a new manner, is proposed. This method solves the above-mentioned two problems by optimizing the learning process, especially learning rate, by genetic mutations and by locality-controlled parallel search. Initial experimental results shows that LOG-BP performs better; that is, when required, learning rate decreases exponentially and the distances between chromosomes, which indicate the locality of a search, also decrease exponentially.

3D printing of generative art using the assembly and deformation of direction-specified parts

Kanada, Y. / Rapid Prototyping Journal, Vol. 22, No. 4, 2016 / 2016-05-06

A methodology for designing and printing 3D objects with specified printing-direction using fused deposition modelling (FDM), which was proposed by a previous paper, enables the expression of natural directions, such as hairs, fabric, or other directed textures, in modelled objects. This paper aims to enhance this methodology for creating various shapes of generative visual objects with several specialized attributes. The proposed enhancement consists of two new methods and a new technique. The first is a method for “deformation.” It enables deforming simple 3D models to create varieties of shapes much more easily in generative design processes. The second is the spiral/helical printing method. The print direction (filament direction) of each part of a printed object is made consistent by this method, and it also enables seamless printing results and enables low-angle overhang. The third, i.e., the light-reflection control technique, controls the properties of filament while printing with transparent PLA. It enables the printed objects to reflect light brilliantly. ...

手続き抽象化機能をもつプログラミング言語による 3D 印刷

Kanada, Y. / 情報処理学会 プログラミング研究会 2015 年度 第 5 回, 2016-2 / 2016-02-28

When manufacturing or 3D-printing a product using a computer, a program that procedurally controls manufacturing machines or 3D-printers is required. G-code is widely used for this purpose. G-code was developed for controlling of subtractive manufacturing, and a designer historically wrote programs in G-code; however, in recent development environments, the designer describes a declarative model by using CAD, and the computer converts it to a G-code program. However, because the process of additive man- ufacturing, such as 3D printing, is more intuitive than subtractive manufacturing, it sometimes seems to be advantageous to describe an abstract procedural program by the designer for this purpose. This paper, thus, proposes a method for generating G-code by describing an abstract Python program using a library for procedural 3D-design and for printing by a 3D printer, and shows use cases. Although shapes printable by this method are restricted, this method can eliminate layers and layer seams and eliminate support material, which is necessary for conventional methods when an overhang exists, and it enables seamless and artistic printing.

Self-organized 3D-printing Patterns Simulated by Cellular Automata

Kanada, Y. / Y. Suzuki and M. Hagiya, ed., Recent Advances in Natural Computing, 2016 / 2016-01-01

3D printers are usually used for printing objects designed by 3D CAD exactly, i.e., deterministically.However, 3Dprinting process contains stochastic selforganization process that generate emergent patterns. A method for generating fully self-organized patterns using a fused depositionmodeling (FDM) 3D printer has been developed. Melted plastic filament is extruded constantly in this method; however, by using thismethod, various patterns, such as stripes, splitting and/or merging patterns, and meshes can be generated. A cellular-automata-based computational model that can simulate such patterns have also been developed.

Designing 3D-Printable Generative Art by 3D Turtle Graphics and Assembly-and-Deformation

Kanada, Y. / XIIIV Generative Art Conference (GA 2015), 2015-12 / 2015-12-11

3D models are usually designed by 3D modelling tools, which are not suited for generative art. This presentation proposes two methods for designing and printing generative 3D objects. First, by using a turtle-graphics-based method, the designer decides self-motion (self-centered motion) of a turtle and print a trajectory of the turtle as a 3D object (Fig. A). The trajectory is printed using a fused-deposition-modelling (FDM) 3D printer, which is the most popular type of 3D printer. Second, by using the assembly-and-deformation method, the designer assembles parts in a palette, each of which represents stacked filaments, applies deformations to the assembled model, and prints the resulting object by an FDM 3D printer. The designer can also map textures, characters, or pictures on the surface of the object. Various shapes can be generated by using the assembly-and-deformation method. If the initial model is a thin helix with a very low cylinder (i.e., an empty cylinder with a bottom), shapes like cups, dishes, or pods with attractive brilliance can be generated, and a globe and other shapes can be generated from a helix (Fig. B).

Creating Thin Objects with Bit-mapped Pictures/Characters by FDM Helical 3D Printing

Kanada, Y. / 8th International Conference on Leading Edge Manufacturing in 21st Century (LEM 21), 2015-10 / 2015-10-18

Instead of printing layer by layer, thin 3D objects can be printed in better quality (without seams between layers) by printing helically or spirally by fused deposition modeling (FDM). When printing helically or spirally, the amount of extruded filament can be modulated using a bitmap; that is, “zero” in bitmap means “thin” and “one” means “thick” (or vice versa). This process generates a thin object, such as a sphere, pod, or dish, with a bitmapped picture or characters. A typical example is a globe, which is printed using a bitmapped world map.

手続き的な方法による工業製品設計

Kanada, Y. / 日本機械学会 2015 年度年次大会, G120 設計工学・システム部門一般セッション, 2015-9 / 2015-09-14

As well as in computer programming, both declarative and procedural methods should be available in industrial product design. However, design for 3D printing is mostly based on declarative CAD as well as other areas of product design. This presentation reports a method for generative (procedural) design.

方向指定つきの 3D 印刷法と設計法

Kanada, Y. / 日本機械学会 2015 年度年次大会, S044 次世代 3D プリンティング, 2015-9 / 2015-09-14

In 3D printing methods such as FDM, the direction of printing dominates the appearance and the nature of the printed objects. However, the direction cannot be specified in conventional 3D-printing methods. In this presentation, methods for designing and printing direction-specified 3D objects and the advantages of these methods are described.

Support-less Horizontal Filament-stacking by Layer-less FDM

Kanada, Y. / International SFF Symposium 2015, August 2015 / 2015-08-01

Material is stacked vertically and layer-by-layer in conventional additive manufacturing (AM) methods. An object with overhang or skewed stacking structure, such as a plain dish or an empty sphere, is difficult to be created by these methods without support material. This paper proposes a layer-less fused-deposition-modeling (FDM) method that enables mostly horizontal stacking of filament without support material. Such filament-stacking is enabled by increasing the height of the print head gradually, i.e., without layer transitions that make horizontal stacking difficult. The proposed method also allows controlling printing directions and various printing-direction-dependent expressions, such as fiber-like textures or brilliance, which make AM products attractive as final products for consumers or as some kinds of industrial products. Objects to be printed can be modeled as directed solid models designed by a component-based method (i.e., a new CAD based method) or a generative method, which are completely different from conventional CAD based methods.

Let's enjoy such "naturally designed" patterns!

Kanada, Y. / 2015-07-24

「3D プリンタ」で自然のデザインを楽しもう

金田 泰 / 2015-07-24

「3D プリンタ」では通常は人工的にデザインしたものを印刷しますが，意図せずに出来るパターンもあります．こういう「自然のデザイン」を，積極的に楽しんでみましょう．

Federating Heterogeneous Network Virtualization Platforms by Slice Exchange Point

Tarui, T., Kanada, Y., Hayashi, M., Nakao, A. / IFIP/IEEE International Symposium on Integrated Network Management (IM 2015), 2015-5 / 2015-05-01

An architecture called the slice-exchange-point (SEP) has been designed for federating heterogeneous net-work-virtualization platforms by creating and managing slices (virtual networks). SEP enables whole inter-domain resources to be managed by the network manager of any single domain. Slice-operation commands are propagated to other domains through SEP by using a common API. SEP introduces the following four features: infrastructure neutrality, single interface federation, abstract and clean federation, and extensibility of capabilities. SEP's functions to achieve these features are discussed. SEP was partially implemented on two VNode domains and one ProtoGENI domain and was verified to function effectively.

3D プリンタ「サポート」なしで皿をつくる

Kanada, Y. / I/O 2015-4. / 2015-03-21

3D プリンタを使ってひらたい皿をつくるとき，普通は「サポート」という，印刷がおわると捨ててしまう材料をいっしょに印刷して，それで皿をささえる必要があります．でも，そんなもったいないものをつかわずに，うすい皿を造形してみましょう．ちょっとした工夫が必要ですが，そんなに難しいことではありません．

IPON: Switching by IP Addresses

Kanada, Y. / 第 13 回ネットワーク仮想化研究会, March 2015 / 2015-03-16

High-Level Portable Programming Language for Optimized Memory Use of Network Processors

Kanada, Y. / Communications and Network, Vol. 7, pp. 55-69 / 2015-02-19

Ethernet Switch/terminal Simulators for Novices to Learn Computer Networks

Kanada, Y. / 29th edition of the International Conference on Information Networking (ICOIN 2015), January 2015 / 2015-01-10

Federation-less Federation of ProtoGENI and VNode Platforms

Kanada, Y., Tarui, T. / 29th edition of the International Conference on Information Networking (ICOIN 2015), January 2015 / 2015-01-10

3D-printing of Generative Art by using Combination and Deformation of Direction-specified 3D Parts

Kanada, Y. / 4th International Conference on Additive Manufacturing and Bio-Manufacturing (ICAM-BM 2014, Beijing), 2014-11 / 2014-11-15

Direction-specified 3D modeling and FDM-based printing methods enable expression of natural directions, such as hairs, fabric, or other directed textures, in modeled objects. This paper describes a method for creating various shapes of generative artistic objects with several specialized attributes by applying three new techniques to the direction-specified methods for better artistic expressions. The most important technique is “deformation”, which enables deforming simple 3D models to create varieties of shapes much more easily in generative design processes. The second technique is called the spiral/helical printing method, which enables consistent print-direction vector field, i.e., filament directions, of the surface consistent with those of the interior portion and enables seamless or less-seam printing results. The third technique controls light reflection while printing by using the spiral/helical printing method with transparent PLA. It enables the printed objects reflect light brilliantly. The proposed method with these three techniques was implemented as a Python library and evaluated by printing various shapes, and it is confirmed that this method works well and objects with attractive attributes can be created.

3D プリンタによる “3 次元タートル・グラフィクス”

Kanada, Y. / 情報処理学会 夏のプログラミング・シンポジウム 2014, 2014-8 / 2014-08-09

3D プリンタで造形するとき，通常は 3D CAD で設計した静的 (宣言的) なモデルのデータを加工してプリンタにおくる． しかし，普及している FDM 型 3D プリンタが入力するのはプリント・ヘッドの移動とフィラメントの射出を制御する動的な手続きであり，これをより素直にプログラミング言語化ないしライブラリ化すれば，タートル・グラフィクスのような方法で 3D オブジェクトが生成できる． この 「タートル 3D 印刷」 のライブラリを Python によって記述し試用してみた． このライブラリは公開している． 3D プリンタでは宙に印刷できないことがネックになるが，その問題をうまくクリアできれば 3D タートル・グラフィクスでえがいた図形を実物にすることができる．

Extending Network-virtualization Platforms by using a Specialized Packet Header and Node Plug-ins

Kanada, Y. / 22nd International Conference on Software, Telecommunications and Computer Networks (SoftCom 2014), September 2014 / 2014-08-01

A previously developed plug-in architecture for network-virtualization nodes allows network operators to introduce new types of virtual nodes and links and slice developers to use them in slices (i.e., virtual networks). In this paper, a method for extending network-virtualization infrastructures by introducing plug-ins to nodes in the infrastructure and a freely-designed plug-in-specific packet header, which enable sharing part of packet contents among the same type of plug-ins distributed in the infrastructure, is proposed. The header is inserted into every data packet handled by the nodes, but it is hidden from slices in a “clean virtualization” infrastructure. This method was applied to creation of a new type of virtual links with network-delay measurement function using a hidden timestamp in each packet. The timestamps do not affect slices; that is, conventional programs can be used in the slice for the measurement without modification. The method was evaluated by edge-to-edge delay measurements and the evaluation results show that it is suitable for developing new functions, including functions requiring wire- rate performance, in shared/public networks.

Providing Infrastructure Functions for Virtual Networks by Applying Node Plug-in Architecture

Kanada, Y., Tarui, T. / Network Virtualization Symposium 2014, July 2014 / 2014-08-01

Providing Infrastructure Functions for Virtual Networks by Applying Node Plug-in Architecture

Kanada, Y. / Procedia Computer Science, Vol. 34, pp. 661-667, 2014 / 2014-08-01

Although nodes in a network-virtualization infrastructure, which is called a virtualization node, usually contain a switch or a router with sophisticated and high-performance functions such as Ethernet switching, VLAN, and IP routing, most of such infrastructure functions cannot be reused as program components by slices. Accordingly, a method for providing such functions to slices on a virtualization node (VNode) infrastructure, by applying the previously proposed plug-in architecture, is proposed. This architecture defines two types of plug-ins, i.e., control plug-ins and data plug-ins, and interfaces for them. As for the proposed method, the switch or router in the VNode is regarded as a data plug-in, and a control plug-in that allocates and isolates the switch/router resources was developed. The data plug-in interface was customized to handle a data plug-in, i.e., a layer-3 switch in a VNode, and a control plug-in and the interfaces for providing layer-3/VLAN switch functions to slices were designed, implemented, and evaluated. The evaluation result shows that instead of specifying a routing/switching program or method, specifying only an additional 8 to 25 lines in a slice definition enables slice developers to use routing and switching functions.

Method of Designing, Partitioning, and Printing 3D Objects with Specified Printing Direction

Kanada, Y. / 2014 International Symposium on Flexible Automation (ISFA 2014), 2014-7 / 2014-07-12

Although 3D objects to be printed may have “natural direction” or intended direction for printing, most 3D printing methods slice and print them horizontally. This causes staircase effect on the surface and prevents expression of the natural or intended direction; that is, the natural direction and the printing direction contradict. This paper proposes a methodology for direction-specified 3D printing and methods for designing, partitioning, and printing 3D objects with specified printing direction using a fused deposition modeling (FDM) printer. By using these methods, printed objects do not only have unnatural steps but also enables to express the direction explicitly. By developing and evaluating a set of methods based on this methodology, chained rings of an Olympic symbol are designed, partitioned, and printed by a delta-type 3D printer, which is cheaper but can move quick vertically. The rings were well designed and printed rings look well. Although there are still several unsolved problems including difficulty in deciding part partition points and weakness in the partition points, this methodology will probably enable new applications of 3D printing, such as 3D calligraphy.

Self-organized 3D-printing Patterns Simulated by Cellular Automata

Kanada, Y. / 20th International Workshop on Cellular Automata and Discrete Complex Systems (Automata 2014), July 2014 / 2014-07-07

3D printers are usually used for printing objects designed by 3D CAD exactly, i.e., deterministically. However, 3D printing process contains stochastic self-organization process that generate emergent patterns. A method for generating fully self-organized patterns using a fused deposition modeling (FDM) 3D printer has been developed. Melted plastic filament is extruded constantly in this method; however, by using this method, various patterns, such as stripes, splitting and/or merging patterns, and meshes can be generated. A cellular-automata-based computational model that can simulate such patterns have also been developed.

Developing Revolutionary 3D Design and Printing Methods

Kanada, Y. / BIT’s 1st Annual International Congress of 3D Printing, Dalian, China, June 27-29, 2014 / 2014-06-28

High-level Portable Programming Language for Optimized Memory Use of Network Processors

Kanada, Y. / ACM SIGPLAN Workshop on Memory Systems Performance and Correctness (MSPC 2014), poster, June 2014 / 2014-06-16

Controlling Network Processors by using Packet-processing Cores

Kanada, Y. / 2nd International Workshop on Network Management and Monitoring (NetMM 2014), May 2014 / 2014-05-17

A Method for Evolving Networks by Introducing New Virtual Node/link Types using Node Plug-ins

Kanada, Y. / 1st IEEE/IFIP International Workshop on SDN Management and Orchestration (SDNMO 2014), May 2014 / 2014-05-13

FDM 3D-printing as Asynchronous Cellular Automata

Kanada, Y. / 8th International Workshop on Natural Computing (IWNC 2014), 2014-3 / 2014-02-21

Fused deposition modeling (FDM) is a 3D-printing method that shapes 3D objects by layering melted plastic filament. The process of this type of 3D printing can be regarded as asynchronous cellular-automata because it generates 1D on-off pattern per a head motion. Especially, by a constant head-motion at reduced constant extrusion-velocity, a 3D printer can generate self-organized grids or similar structures, which is much finer than artificial (i.e., program-controlled) patterns. Depending on the parameter values, i.e., layer depth, extrusion velocity, and so on, the generated pattern varies among regular stripes, stripes with crossing waves, and splitting and merging patterns. Some of the patterns can be simulated by a computational model, i.e., asynchronous cellular automata.

3D Printing and Simulation of Naturally-Randomized Cellular-Automata

Kanada, Y. / 19th International Symposium on Artificial Life and Robotics (AROB 2014), 2014-1 / 2014-01-22

3D printing technology usually aims reproducing objects deterministically designed by 3D CAD tools. However, 3D printing can generate patterns similar to randomized (non-deterministic) 1D or 2D cellular automata (CA). Cheap fused deposition modeling (FDM) 3D printers can be used for this purpose. By using an FDM 3D printer, melted plastic filament is extruded by a hot nozzle to shape a 3D object. They can generate CA-like patterns with constant head motion and constant filament extrusion and with unintended fluctuation but no explicit randomness. Because of fluctuation, every time the printer generates a different emergent pattern. This paper proposes a method for printing seaweed-like patterns of 1D and 2D CA using FDM, and computational CA models. This method will open a new horizon of 3D printing applications.

A Node Plug-in Architecture for Evolving Network Virtualization Nodes

Kanada, Y. / 2013 Workshop on Software Defined Networks for Future Networks and Services (SDN4FNS 2013), November 2013 / 2013-11-13

Virtualization nodes, i.e., physical nodes with network virtualization functions, contain computational and networking components. Virtualization nodes called “VNodes” enabled mutually independent evolution of computational component called programmer and networking component called redirector. However, no methodology for this evolution has been available. Accordingly, a method for evolving programmer and redirector and developing new types of virtualized networking and/or computational functions in two steps is proposed. The first step is to develop a new function without updating the original VNode, which continues services to existing slices, using a proposed plug-in architecture. This architecture defines predefined interfaces called open VNode plug-in interfaces (OVPIs), which connect a data and a control plug-ins to a VNode. The second step is to merge the completed plug-ins into the original programmer or redirector. A prototype implementation of the above plug-in architecture was developed, tested, and evaluated. The prototype extends the redirector by adding new types of virtual links and new types of network accommodation. Estimated throughputs of a VLAN-based network accommodation and a VLAN-based virtual link using network processors are close to a wire rate of 10 Gbps.

Maker Faire Tokyo 2013 のフライヤー等

Kanada, Y. / Maker Faire Tokyo 2013, 2013/11/3-4 / 2013-11-06

A VNode Plug-in Architecture to Evolve VNode

Kanada, Y., Tarui, T. / Network Virtualization Symposium 2013, September 2013 / 2013-09-09

A Method of 3D Printing which is Consistent with Natural Direction in Shape

Kanada, Y. / International SFF Symposium 2013, August 2013 / 2013-08-06

Usually, objects are horizontally sliced when printed by 3D printers. Therefore, if an object to be printed, such as a collection of fibers, originally have natural direction in shape, the printed direction contradicts with the natural direction. By using proper tools, such as field-oriented 3D paint software, field-oriented solid modelers, field-based slicing algorithms, and non-horizontal FDM 3D printers, the natural direction can be modeled and objects can be printed in a direction that is consistent with the natural direction. This consistence results in embodiment of momentum or force in expressions of the printed object. To achieve this goal, several manufacturing problems, but not all, have been solved. An application of this method is (Japanese) 3D calligraphy.

ネットワーク・プロセッサのためのオープンで高級で移植可能なプログラミング環境

Kanada, Y. / 電子情報通信学会 第 7 回 ネットワーク仮想化時限研究会, July 2013 / 2013-07-19

ネットワーク・プロセッサは高性能でプログラマブルなネットワークのためにひろく使用されている． しかし，ネットワーク・プロセッサのプログラムは移植性と開発者数がかぎられ，開発コストが高い． この問題を解決するためにオープンで高級かつ移植性のあるプログラミング言語 CSP とそのための開発環境 +Net を開発した． この環境においては，パケットの高速処理に必要な SRAM と DRAM のつかいわけをプログラマにできるだけ意識させずに高 いスループットがえられるようにした． ネットワーク・プロセッサ Cavium Octeon のためのプロトタイプを実装し，ネット ワーク仮想化基盤の一部を使用して評価した結果，かんたんなプログラムでワイヤレートにちかい 7.5 Gbps 以上の 性能をえた．

Federation-less-federation of Network-virtualization Platforms

Kanada, Y., Tarui, T., Shiraishi, K. / IFIP/IEEE International Symposium on Integrated Network Management (IM 2013), 2013-5 / 2013-06-02

A method for federating multiple network-virtualization platforms by creating and managing slices (virtual networks) is proposed. A cross-domain slice can be created, deleted, or modified by sending a slice specification to the domain controller (network manager) of one domain. The specification is then propagated to other domains. Two chal­lenges were addressed while this method was developed. The first challenge is to enable federation among multiple domains that do not support federation functions by only adding a few components without modification of the existing network-virtualization-platform architecture. A domain-dependent specification of a slice, containing a pseudo virtual node that encloses a part of the slice specification in the other domains, is used, and this part is handled by a proxy node that represents another domain and a control component that implements a federation API to create a cross-domain slice. The second challenge is to enable manageable non-IP (arbitrary-format) data communication on a cross-domain slice. For an inter-domain communication, underlay VLAN parameters including MAC addresses are negotiated in advance and data packets on a slice are tunneled between gateways in these domains. The proposed federation method was implemented on two network-virtualization platforms, federation between two homogeneous domains was successfully demonstrated, federation perfor­mance was measured, and several issues on functional restrictions and implementation difficulty were found.

Network-resource Isolation for Virtualization Nodes

Kanada, Y., Shiraishi, K., Nakao, A. / IEICE Trans. Commun., Vol. E96-B, No. 1, pp. 20-30, 2013 / 2013-01-01

One key requirement for achieving network virtualization is resource isolation among slices (virtual networks), that is, to avoid interferences between slices of resources. This paper proposes two methods, per-slice shaping and per-link policing for network-resource isolation (NRI) in terms of bandwidth and delay. These methods use traffic shaping and traffic policing, which are widely-used traffic control methods for guaranteeing QoS. Per-slice shaping utilizes weighted fair queuing (WFQ) usually applied to a fine-grained flow such as a flow from a specific server application to a user. Since the WFQ for fine-grained flows requires many queues, it may not scale to a large number of slices with a large number of virtual nodes. Considering that the purpose of NRI is not thoroughly guaranteeing QoS but avoiding interferences between slices, we believe per-slice (not per virtual link) shaping satisfies our objective. In contrast, per-link policing uses traffic policing per virtual link. It requires less resource and achieves less-strict but more-scalable isolation between hundreds of slices (500 to 700 slices in estimation). Our results show that both methods perform NRI well but the performance of the former is better in terms of delay. Accordingly, per-slice shaping (with/without policing) is effective for delay-sensitive services while per-link policing may be sufficiently used for the other types of services.

Network-virtualization Nodes that Support Mutually Independent Development and Evolution of Node Components

Kanada, Y., Shiraishi, K., Nakao, A. / 13th IEEE International Conference on Communication Systems (ICCS 2012), November 2012 / 2012-11-27

“Virtualization nodes” (VNodes) for programma­ble network-virtualization platforms are being developed. Criteria for “clean” network-virtualization are devised and applied to this platform and slices (virtual networks). These criteria meet one of the challenges targeted by the Virtualization Node Project, that is, to enable mutually independent development and evolution of compo­nents (namely, computational compo­nents called programmers and networking compo­nents called redirectors) in VNodes. To meet this challenge, the redirector plays the central role in implementing the following two functions of VNodes. The first function is creation of mapping between virtual links to external physical paths and mapping between virtual links to internal physical paths, which makes it possible to hide various alterna­tive computa­tional components in the VNode from the external network and to hide these external-network representa­tions from the internal compo­nents. The second function is imple­mentation of high-performance data conversion, which connects the exter­nal and internal data formats or mappings, by using an add-on card with a network processor. Two results are obtained from the performance evaluation of these functions. First, the overhead caused by mapping creation can be hidden by other tasks under normal conditions, but the overhead caused by mapping deletion must be reduced. Second, the data-conversion rate is half the wire rate, which should be increased in future work.

High-performance Network Accommodation and Intra-slice Switching Using a Type of Virtualization Node

Kanada, Y., Shiraishi, K., Nakao, A. / IARIA Infocomp 2012, 2012-10-24 / 2012-10-17

The architecture for programmable networkvirtualization platforms, i.e., the VNode architecture, has been developed in a project called the Virtualization Node Project. This paper introduces a type of physical node called Network ACcommodation Equipment (NACE) to the VNode architecture. NACE has dual roles in this architecture. The first role is as a network-slice gateway between an external network (Ethernet/VLAN) and a slice (virtual network). NACE can accommodate a data center or another testbed in a slice with high-performance (up to 10 Gbps) data-format conversion. The second role is as a special type of virtualization node that implements intra-slice virtual switch by using Ethernet hardware, which can replace software-based switching using a VM or a network processor. These roles are modeled as a node sliver (virtual node) with a gateway function and a node sliver with a switching function (i.e., a switch node-sliver), and these node slivers are specified by using XML. These functions were evaluated by using two testbeds, and the evaluation results confirm that both functions work correctly and perform well in terms of delay and packet loss.

ネットワーク仮想化基盤における仮想ノード間とスライス-外部ネットワーク間の接続機能

Kanada, Y., Shiraishi, K., Nakao, A. / 電子情報通信学会 ネットワーク仮想化時限研究会, 2012-3-5 / 2012-10-17

On the network virtualization platform that consists of multiple virtualization nodes (VNodes), multiple slices (virtual networks) can be operated simultaneously while isolated from other slices. Virtual nodes (node slivers) can be connected freely by using virtual links (link slivers) at up to 10-Gbps, and arbitrary protocol, which is not constrained by Ethernet or IP, can be used on the slice. VNodes implement virtual links on IP networks by using GRE tunnels. In addition, by using a network accommodation equipment (NACE, NC) that translates the packet data format to an external format, slices can be connected to external VLAN networks at up to 10-Gbps. This paper describes how such connections are referenced and defined by slice developers and how they are translated and physical communication is realized.

「クリーンな仮想化」 と要素独立進化型の 仮想化ノード・アーキテクチャ

Kanada, Y., Nakao, A. / 電子情報通信学会 ネットワーク仮想化時限研究会 第 3 回, 2012-3-2 / 2012-03-06

In a collaboration project, the virtualization node (VNode) and the virtualization platform are developed. A feature of VNode is architecture that supports independent component-evolution. In this presentation, we propose clean-virtualization concept, and show that VNode realizes this concept, and that this concept is important to implement architecture that supports independent component evolution. In addition, we show the method of implementing the architecture and realizing the condept in VNode, especially the implementation of the architecture in the redirector, a part of VNode.

Development of A Scalable Non-IP/Non-Ethernet Protocol With Learning-based Forwarding Method

Kanada, Y., Nakao, A. / World Telecommunication Congress 2012 (WTC 2012), 2012-3-5 / 2012-03-06

We have developed an experimental non-IP/non-Ethernet protocol called IPEC (IP Ether Chimera). IPEC switches learn IPEC addresses that are structured hierarchically, similar to IP addresses, using an algorithm that extends the learning algorithm of Ethernet switches. IPEC is a simple non-IP network-layer protocol that has features of both Ethernet and IP. Unlike IP, IPEC introduces an address group to manage multiple terminals as a group to make learning of mobile terminals more scalable and more efficient than Ethernet. Because an address group is the unit of learning in IPEC, it is more scalable than Ethernet, and mobile groups can be learned more efficiently. In addition, IPEC tolerates loops in a network as long as a limited number of duplicate packets are allowed, and thus, enable an alternative route against link failures. We have implemented IPEC both on an IPEC-capable switches using LAN cards and on a virtual network using virtualization nodes (VNodes), which have been developed to experiment with non-IP protocols such as IPEC. We show evaluations that the group learning function of IPEC is viable especially for multiple terminals moving together concurrently.

フェデレーション機能をもたない仮想化基盤のフェデレーション

金田 泰, 垂井 俊明 / 電子情報通信学会 ネットワーク仮想化時限研究会 第 2 回, 2011-11-10 / 2011-11-11

In collaboration projects funded by NICT, we develop a mechanism of federation among the virtualization platform developed by the Virtualization Node Project and G-lambda, ProtoGENI, and other platforms. This mechanism enables generation and management of slices extending through the virtualization platforms. We presents a method for enabling federation without recreating the virtualization platform without federation function, but only by adding additional functions.

仮想ネットワーク・モデルにもとづく VM 広域ライブマイグレーションの設定法の開発

金田 泰 / 情報処理学会論文誌, Vol. 52, No. 3, pp. 1-17, 2011 / 2011-02-11

ネットワーク仮想化は，ひとつの物理的なネットワーク上で多様なサービスを相互に干渉せず実現し，かつ単純にプログラムしカスタマイズすることを可能にする． ネットワーク仮想化は，IP，VLAN，あるいは NAT を使用するなど，多様な機構によって実現できる． 我々はこれらの実現手段に依存しない統一的な仮想ネットワークのモデルをつくり，そのモデルによって記述した仮想ネットワークを基本的に変更せずに多様な実現手段のネットワーク上に展開可能にすることをめざしている． この論文では仮想ネットワークのモデルとその主要な部品を定義し，それによって広域ライブ・マイグレーションのための仮想ネットワークを記述し，さらにそれをネットワーク・パーティション (VLAN による VRF) とアドレス・マッピング (NAT) という 2 つの実現方法による仮想ネットワークに展開できることを示す． この方法を仮想ネットワーク設定プロトタイプを新規開発して評価した． その結果，アドレス範囲指定やルーティング・パラメタの指定は実現手段ごとに変更する必要があったが，モデル記述の主要部分は共通化できた．

Address-Translation-Based Network Virtualization

Kanada, Y., Tarui, T. / 10th International Conference on Networks (ICN 2011), 2011-1-24 / 2011-01-24

Two network-virtualization architectures, namely, network segmentation and network paging, were investigated. They are analogical to two memory-virtualization architectures: segmentation and paging. Network paging, which is relatively new and is based on a type of network-address translation (NAT), is focused on. This architecture requires smaller packet size and has several more advantages over the conventional architecture (i.e., network segmentation). Intranet- and extranet- type communication methods based on this architecture are described. An address translators is placed at each edge router in the WAN and used to evaluate client-server communication under wide-area virtual-machine (VM) live migration as a case of extranet-type communication.

仮想化ノードを使用した実験用非 IP プロトコルの開発

Kanada, Y., Shiraishi, K., Nakao, A. / 電子情報通信学会情報ネットワーク (IN) 研究会, 2010-9-2 / 2010-09-04

In the National Institute of Information and Communications Technology (NICT), 10-Gbps-class virtualization nodes (VNodes) that enables implementing non-IP protocols with any frame format are developed using network-virtualization technology. We have developed an experimental non-IP protocol called IPEC (IP Ether Chimera) on a virtual network us-ing the VNodes. In IPEC, the nodes learn addresses that can be hierarchical such as IP addresses using an algorithm that extends Ethernet switch learning algorithm. IPEC has the following features. First, IPEC realizes a simple single-layer non-IP protocol that has features of both Ethernet and IP. Second, because a group is the unit of learning in IPEC, it is more scalable than Ethernet, and mobile groups can be more efficiently learned. Third, this forwarding algorithm can be used in networks with loops and it can forward packets during failure using an alternative route. Group IDs can be used as locators, so IPEC can be regarded to realize an architecture that extends ID/Locator separation architecture. We implemented IPEC on VNodes, and confirmed that it enabled group learning and group mobility by experiments.

Fine-grained Full-text Search

Kanada, Y. / 2009-07-18

Most conventional text retrieval methods are designed to search for documents. However, users often do not require documents themselves, but are searching for spe-cific information that may come from a large collection of texts quickly. To satisfy this need, we have developed a model and two methods for fine-grained searching. The unit of search in this model is called an atom, and it can be a sentence or smaller syntactic unit. A score, i.e., a relevance value, is defined for each atom and for each query, and the score is propagated between atoms. By using the two methods, excerpts from texts surrounding the search-result items and/or hyperlinks to the document parts that include the items are displayed. Multiple topics in a document can be separately listed in a search result. Evaluation of two prototypes, using a conventional full-text search engine as is or with only a small modification, has demonstrated that these methods are feasible and can decrease the search cost in terms of time and effort for users.

ユーザ・レベルの通信品質要求を満足させるネットワーク制御機構の開発

Kanada, Y. / 電子情報通信学会情報ネットワーク (IN) 研究会, 2009-5-21 / 2009-05-21

A mechanism for users to input a request on quality of experience (QoE) and for the network to satisfy the request. A QoE request is mapped to QoS, and it is satisfied by using admission control and network node configurations. By using a soft-state protocol for the request, service initiation, extension, and termination are handled in a unified method. Part of this mechanism has been built into a prototype, and tested using a network node with so-called hierarchical shaper and using video streaming, the mechanism has been confirmed to work in a designed way.

A Method of Admission Control Based on Both Resource Requests and Traffic Measurement and Its Dynamics Under On/Off Model Traffic

Kanada, Y. / 5th Advanced International Conference on Telecommunications (AICT 2009), May 2009 / 2009-05-20

A method of admission control based on both resource requests by applications and class-based traffic mea-surement results was developed. In this method, a wide range of admission-control policy can be realized by adjusting three parameters, , , and . A policy-server prototype using this method and simulated voice traffic was used in traffic measurements. The measurements results show that the proposed method improves bandwidth usage and decreases call-blocking ratio while incurring low measurement load. Interesting but possibly harmful dynamics (i.e., system behavior) were observed by the simulations using traffic generated by an on/off model. That is, this admission-control method may cause oscillation or long-term evolution that lasts for 100 to 150 minutes, and it may also cause bandwidth “overshooting”. The range of parameters with which such effects can be properly suppressed and the admission control correctly works was experimentally obtained.

資源要求とトラフィック計測結果の両方にもとづくアドミッション制御法と その On/Off モデルのもとでのダイナミクス

Kanada, Y. / 電子情報通信学会ネットワークシステム (NS) 研究会, 2009-4-16 / 2009-04-20

A method of admission control based on both resource requests by applications and traffic measurement results per DiffServ class using NetFlow was developed. Several experiments using a newly-developed policy-server prototype using this method and simulated voice traffic showed that bandwidth usage can be improved and call blocking ratio was decreased with low measurement load by using this method. Interesting but possibly harmful dynamics were observed by simulations using simulated traffic that follows an on/off model; i.e., this admission control method may cause oscillation or long-term development that lasts for 100 to 150 minutes, and it may also cause bandwidth overshooting. The range of parameters, with which such phenomena can be properly suppressed and the admission control correctly works, was experimentally obtained.

Policy-based End-to-End QoS Guarantee Using On-Path Signaling for Both QoS Request and Feedback

Kanada, Y. / The International Conference on Information Networking 2008 (ICOIN 2008), I-1, January 2008 / 2008-01-03

Real-time and multimedia applications require an end-to-end QoS guarantee, and various types of applications require various QoS conditions. A DiffServ network should guarantee different QoS conditions for different types of communications. In this paper, the effect of traffic control in a DiffServ core network is experimentally evaluated using bursty traffic generated by an MMPP (Markov-Modulated Poisson Process) model. The situation to be simulated is that there are hundreds of conversational video streams that are delay-sensitive and hundreds of streaming videos that are loss-sensitive. If there are bandwidth-sharing queues such as those follow WFQ (Weighted Fair Queuing) in the core no-des and the two types of video traffic are assigned to two of the queues, the requirements of both types of traffic can be satisfied in a better way (a more efficient way) by assigning a larger weight to the queue for the conversational video. In our experiment, the optimum ratio of the weights was ap-proximately 1.3 when the traffic rates were the same. The optimum weight shares depend on the nature of the traffic, especially the burstiness.

Method of DiffServ-Based Bandwidth-Sharing among Delay-Sensitive Traffic and Loss-Sensitive Traffic in Backbones

Kanada, Y. / 未出版 (2008-4). / 2007-11-30

Real-time and multimedia applications require an end-to-end QoS guarantee, and various types of applications require various QoS conditions. A DiffServ network should guarantee different QoS conditions for different types of communications. In this paper, the effect of traffic control in a DiffServ core network is experimentally evaluated using bursty traffic generated by an MMPP (Markov-Modulated Poisson Process) model. The situation to be simulated is that there are hundreds of conversational video streams that are delay-sensitive and hundreds of streaming videos that are loss-sensitive. If there are bandwidth-sharing queues such as those follow WFQ (Weighted Fair Queuing) in the core no-des and the two types of video traffic are assigned to two of the queues, the requirements of both types of traffic can be satisfied in a better way (a more efficient way) by assigning a larger weight to the queue for the conversational video. In our experiment, the optimum ratio of the weights was ap-proximately 1.3 when the traffic rates were the same. The optimum weight shares depend on the nature of the traffic, especially the burstiness.

パスにそったシグナリングにもとづく QoS 保証法の設計と試作

Kanada, Y. / 電子情報通信学会 通信ソサイエティ大会, 2007-9 / 2007-09-11

仮想の “音の部屋” によるコミュニケーション・メディア <i>voiscape</i> の主観評価

Kanada, Y. / 電子情報通信学会 応用音響 (EA) 研究会, EA2007-42, 2007-8 / 2007-08-09

Voiscape is a communication medium by which people can talk each other while moving within virtual sound space freely. By using a prototype of voiscape called VPIIQ (Voiscape Prototype II Q), the effect of difference of QoS caused by network policies was evaluated subjectively. The result showed unexpectedly that the percentage of correct answers was higher in the case in which QoS is lower in the localization test. In the sound localization tests, the percentage of correct answers was higher when subjects performed operations to move or to turn than not to do so. However, in the speaker recognition tests, opposite results were observed.

パスにそったシグナリングにもとづく端点間 QoS 保証法の開発と評価

Kanada, Y. / 電子情報通信学会 コミュニケーションクオリティ (CQ) 研究会, 2007-7 / 2007-07-13

RSVP や NSLP にちかいプロトコルによって端末からつたえられる QoS 要求をコア網で集約してスケーラブルな QoS 保証を実現する方式を設計・ 試作した． 要求はポリシールーティングとアウトソース型のプロトコル によってポリシーサーバにつたえられる． ポリシーサーバが要求をもと にトラフィック量を予測してコアノードのキュー (WFQ) の帯域分割を 制御する． このコアノードの制御の効果を L3 スイッチ GS4000 に MMPP モデルにもとづくバースト性トラフィックをとおして評価した． その結果，大量の会話ビデオ・トラフィックとストリーミング・トラ フィックとがあるときに，WFQ における前者のウェイトを後者より たかめれば，しかるべき条件のもとでは両者ともに満足させられること がわかった．

Simulated Virtual Market Place By Using <i>voiscape</i> Communication Medium

Kanada, Y. / 13th ACM International Conference on Multimedia, pp. 794-795, November 2005 / 2005-11-06

We are developing a new voice communication medium called voiscape. Voiscape enables natural and seamless bi-directional voice communication by using sound to create a virtual sound room. In a sound room, people can feel others' direction and dis-tance expressed by spatial sounds with reverberations, and they can move freely by using a map of the room. Voiscape enables multi-voice-conversations. In a virtual market place that will be realized by voiscape, people can not only buy goods or information but also enjoy talking with merchants and people there. In this demo, a vois-cape prototype called VPII is used for realizing such an environ-ment. Unfortunately, because prerecorded voices are used in this demo, the participants cannot talk with merchants. However, the participants can talk each other with small end-to-end latency (less than 200 ms) and will feel the atmosphere of the virtual market place. Prerecorded people and merchants talk each other in English, Japanese and Chinese in parallel and with crossovers, and partici-pants can virtually walk among them and can selectively listen one voice or hear multiple voices at once.

SIP/SIMPLE-based Conference Room Management Method for the Voice Communication Medium "voiscape"

Kanada, Y. / Asia-Pacific Network Operations and Management Symposium 2005 (APNOMS 2005), September 2005 / 2005-09-27

A method for conference-room management for an auditory-virtual-space-based voice-communication medium called voiscape and a voice-communication system prototype called VPII, which used this method, were developed. With this method, conference rooms (called sound rooms) are managed through SIP and SIMPLE (a presence-related event-notification mechanism). A user can not only obtain a room list and enter (select) or exit from a room, but can also create, modify, or delete rooms by SIMPLE messaging. Rooms, users, and objects are managed by their "soft state"; i.e., they are deleted when a time out occurs. Users are informed of room membership, presence of a user, e.g., location and direction in the room, and presence of an object in the room by SIMPLE messaging, i.e., by SUBSCRIBE, NOIFY, and PUBLISH requests. To reduce the messaging overhead, the partial notification mechanism of SIMPLE is used in VPII.

仮想の "音の部屋" によるコミュニケーション・メディア voiscape のための音声 3D 化と残響の計算

Kanada, Y. / 電子情報通信学会 応用音響 (EA) 研究会 / 2005-06-24

We are developing a communication medium called voiscape, which enables taking to people while selecting persons to talk by moving in a virtual "sound room". In the second prototype of voiscape called VPII, the FIR Method is used for low-delay HRTF filtering, the sound room - the range of motion - is identified with the room in acoustical cal-culation, and early reflections by the sound room walls are simulated. The early reflections produce out-of-head sound lo-calization and sound distance expression. We also implemented motion-tracking and interpolation algorithms into the spatialization method. VPII enabled a voice communication environment, in which speaker identification is easy, multiple conversation-contexts can be created in a room, and motions of users and objects in a sound room are natural and causes only small noises.

Multi-Context Voice Communication In A SIP/SIMPLE-Based Shared Virtual Sound Room With Early Reflections

Kanada, Y. / 15th ACM International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV 2005), pp. 45-50, June 2005 / 2005-06-13

An improved prototype of the "voiscape" voice communication medium has been developed and subjectively evaluated. Voiscape enables natural and seamless voice communication by using sound to create a virtual "sound room" in which people, who are represented by different sounds, can move freely. It features low-delay motion-tracking spatial audio with simulated early reflections that produce out-of-head sound localization and sound distance expression. It also features virtual-location-based selective communication: a user can walk freely in the sound room using a map- and cursor-key-based user-interface and can select whom to talk to or which sound sources to listen to. A third feature is SIP-presence-event-notification (SIMPLE)-based sound room management: when users move, their locations and directions are distributed using SIP SUBSCRIBE/NOTIFY messages. The combination of these features creates a natural voice-communication space in which two or more parallel conversation contexts can coexist. Limited, subjective testing by around 200 people showed that this medium can be used for cocktail-party-like conversation; i.e., users could distinguish parallel conversations by paying attention to or by moving toward one of them.

Multi-Context Voice Communication Controlled By Using An Auditory Virtual Space

Kanada, Y. / 2nd IASTED International Conference on Communication and Computer Networks (CCN 2004), 2004-11 / 2004-11-08

A new voice communication medium, which the author calls "voiscape", will probably appear in near future. Voiscape shall have much improved user interface than the conventional voice communication systems, i.e., telephone and conference systems, and be based on the IP-based conferencing and spatial audio technologies. The author has developed a prototype toward voiscape, which has made a step toward solving two problems of the conventional systems i.e., complicated and restricted conference control and lack of crossed-over multi-context support, by introducing two features. The first function is the virtual-location based communication; i.e., the users can talk with other users and move, in a way similar to face-to-face conversation, in a virtual auditory space created by spatial audio technology without explicit session and floor control. The second function is personalized policy-based communication control; i.e., the users can specify communication policies that protects their privacy and reduce required resources. This function is enabled by a distributed policy-arbitration mechanism. Experiments showed that the basic mechanisms and the policy-based control with a simple policy worked well.

仮想の "音の部屋" によるコミュニケーション・メディア voiscape の JMF と Java 3D を使用した実装

Kanada, Y. / 情報処理学会 マルチメディア通信と分散処理研究会, 2004-3 / 2004-03-05

The author researches toward establishing voice communication media called voiscape which shall replace telephone. A virtual "sound room" that is created by spatial audio technology is used in voiscape. We developed a prototype on PCs, in which 3-D graphic is used for supplementing spatial autio. In this prototype, JMF (Java Media Framework) was used for voice capturing and communication, and Java 3D was used for spatial audio and 3-D graphics. Before the development, the author had believed that the basic functions required for the prototype would be realized by connecting these APIs. However, in fact, they cannot be connected directly, so we used OpenAL through the interface of Java 3D. We also encountered problems of sound quality degradation and delay, but they have been almost solved by refining the program by trial and error.

仮想の "音の部屋" によるコミュニケーション・メディア voiscape

Kanada, Y. / 電子情報通信学会 マルチメディアと仮想環境研究会 (MVE / VR 学会 EVR 研究会)，2003-10-7 / 2003-10-08

The concept of a new communication medium called voiscape is proposed. A virtual "sound room" that is based on the spatial audio technology is shared among the users in voiscape, and a person can move freely in the room, can meet and depart from other people, and can talk with two or more persons by using voiscape. By enabling transmission of presence and peripheral information, voiscape will cover from a telephone-style one-to-one conversation to a variety of communication types that are impossible in conventional media, and will enable sharing the feeling of connection and releaf and sharing tacit knowledge. This paper describes usage scenes and a procedure of voiscape and also describes a PC-based prototype. In this prototype, the user can confirm the situation in front by 3D graphics, and can move around the room by using a mouse.

仮想の "音の部屋" によるコミュニケーション・メディア voiscape におけるポリシーベース・セッション制御

Kanada, Y. / 電子情報通信学会 インターネットアーキテクチャ (IA) 研究会, October 2003 / 2003-10-06

As part of research toward establishing voice communication media that shall replace telephone, we developed an architecture and a prototype of a continuously-connected multi-user communication medium called voiscape. A virtual "sound room" that is created by spatial audio technology is used in voiscape. When the user moves within the sound room by using a mouse, the presence information including the position in the room is distributed to other users of the room. If the user becomes closer to or more distant from another user, the communication session begins or ends automatically by using SIP according to predefined policy stored in the terminals. This policy-based session control enables privacy protection and reduction of communication. When a local site requires a session start, the remote site often requires a session start concurrently, so a method of establishing a connection without connecting doubly nor becoming busy was deviced.

Rule-Based Building-Block Architecture for Policy-based Networking

Kanada, Y., Keefe, B. / Journal of Network and Systems Management, Vol. 11, No. 3, pp. 253-275, 2003 / 2003-09-01

We developed two rule-based building-block architectures, i.e., pipe-connection and label-connection architectures, for describing complex and structured policies, especially network QoS policies. The latter is focused on in this study. The relationships or connections between building blocks are specified by the da-taflow and control flow between them. The dataflow is specified by tags, including virtual flow labels (VFLs), which are data attached to "outside packets". The control flow can be classified and specified by four control structures: concatenation, parallel application, selection, and repetition. We have designed fine-grained and coarse-grained building blocks and methods for specifying dataflow and control flow in differentiated services (Diffserv), and implemented the coarse-grained ones in a policy server. Two cases of building-block use are described, and we concluded that there are five advantages of building-block-based policies, i.e., expressibility, uniform semantics, simplicity, flexibility, and management-task-oriented design. We also developed techniques for transforming building-block policies into executable ones, which are called policy division and fusion.

20 世紀の名著名論 Robert W. Floyd: Nondeterministic Algorithms

金田 泰 / 情報処理, vol. 44, No. 2, 2003 / 2003-02-01

Dynamically Extensible Policy Server and Agent

Kanada, Y. / 3rd International Workshop on Policies for Distributed Systems and Networks (Policy 2002), pp. 236-239, June 2002 / 2002-06-05

A Method of Software-Hardware Integration for QoS Policy Combination in Gigabit Routers

Kanada, Y., Yazaki, T. / Communications Quality and Reliability 2002 (CQR 2002), pp. 12-16 2002 / 2002-05-14

In policy-based networks, two or more policies often have to cooperate because combined and customized network functions must be controlled using policies. Two types of policy trans-formation, policy fusion and policy division, are sometimes required to implement cooperating policy systems on high-performance hardware routers. Policy fusion transforms two or more policies into one, and policy division transforms a policy into two or more policies. These transformations causes a problem that the original policies must usually be strongly constrained to allow these transformations. This paper shows a method for resolving restrictions on the division of QoS policies by a software-hardware integration, i.e., by implementing virtual flow labels (flow IDs) in hardware and by dividing a policy and deploying the policies onto two filter blocks. We have developed a policy agent (PEP) and a gigabit router integrated by using this method. Both high-performance and flexibility are achieved by this integration.

IETF 標準化を中心としたポリシー管理技術の動向

Kanada, Y. / 電子情報通信学会 2002 年総合大会，2002-3 / 2002-03-27

(Not available)

Diffserv Policies and Their Combinations in OpenView/JP1 PolicyXpert (Poster paper)

Kanada, Y., Keefe, B. / Asia-Pacific Network Operations and Management Symposium 2001 (APNOMS 2001), September 2001 / 2001-09-26

Policies sometimes have to be combined and applied in cooperation to represent such programmable and customizable network functions as Diffserv. In the OpenView PolicyXpert and JP1/PolicyXpert policy servers, three types of policies and three types of virtual flow labels, to connect the policy rules, are defined for Diffserv. The combination of these policies allows the representation of complex Diffserv policies and the separation of service and subscriber policies. Diffserv policies and virtual flow labels make this possible. However, the careful design of Diffserv policies has enabled simple Diffserv policies to be represented in a simple form.

Policy Division and Fusion: Examples and a Method - or, Multiple Classifiers Considered Harmful

Kanada, Y. / 7th IFIP/IEEE International Symposium on Integrated Network Management (IM 2001), pp. 545-560, May 2001 / 2001-05-14

Because higher- and lower-level policies do not necessarily correspond one to one, a higher-level network policy may have to be translated into two or more lower-level policies, and two or more cooperating higher-level policies may have to be translated into one lower-level policy. The former transformation is called a policy division, and the latter transformation is called a policy fusion. These transformations can be performed mechanically under restricted conditions as described in this paper. However, in general, they are very complicated and the restrictions cannot be eliminated completely mainly because of existence of multiple packet classifiers in a set of policies. Thus, this paper concludes that they should not be introduced if it is possible. The policy division and fusion can be avoided in certain cases, but they will not probably be able to be avoided in general. If so, the problem should be solved or relaxed by removing harmful classifiers by introducing virtual flow labels and by further studies. In addition, we may have to find a better method to control network devices than policies in the current sense.

Taxonomy and Description of Policy Combination Methods

Kanada, Y. / Workshop on Policies for Distributed Systems and Networks (Policy 2001), Lecture Notes in Computer Science, No. 1995, Springer, pp. 171-184, January 2001 / 2001-01-29

To control complicated and decomposable networking functions, such as Diffserv, two or more policies must cooperate. Combining two or more mutually dependent policies for a specific purpose is called policy combination. Methods of passing information between combined policies can be classified into real tags and virtual tags, or labels and attributes. Policy combinations can be classified into concatenation, parallel application, selection, and repetition. Explicitly specifying policy combinations makes policy systems semantically clearer and better suited to general use, extends the range of functionality, and improves the possibility of optimization. If policy combinations can be specified in a policy system, two types of policy organizations can be distinguished: homogeneous and heterogeneous. Heterogeneous organization is more service-oriented and seems to meet service-management requirements, but homogeneous organization is more device-oriented and may provide better performance.

ネットワークのポリシー制御のための 2 つの部品化アーキテクチャの比較

Kanada, Y. / 電子情報通信学会 情報ネットワーク (IN) 研究会, 信学技法, 100-378, IN 2000-102, pp. 47-54, 2000-10 / 2000-10-20

In a policy-based network, two or more policies must often cooperate to provide a high-level function or policy. To support such building-block policies, two architectures for modeling a set of policies have been developed: pipe-connection architecture and label-connection architecture. It is shown that rule-based building blocks are better for policy-based network control and that the label-connection architecture is currently better. However, the pipe-connection architecture is better in regards to parallelism, which is very important in network environments.

Two Rule-based Building-block Architectures for Policy-based Network Control

Kanada, Y. / 2nd International Working Conference on Active Networks (IWAN 2000), Lecture Notes in Computer Science, No. 1942, pp. 195-210, Springer, October 2000 / 2000-10-16

Policy-based networks can be customized by users by injecting programs called policies into the network nodes. So if general-purpose functions can be specified in a policy-based network, the network can be regarded as an active network in the wider sense. In a policy-based network, two or more policies must often cooperate to provide a high-level function or policy. To support such building-block policies, two architectures for modeling a set of policies have been developed: pipe-connection architecture and label-connection architecture. It is shown that rule-based building blocks are better for policy-based network control and that the label-connection architecture is currently better. However, the pipe-connection architecture is better in regards to parallelism, which is very important in network environments.

A Representation of Network Node QoS Control Policies Using Rule-based Building Blocks

Kanada, Y. / International Workshop on Quality of Service 2000 (IWQoS 2000), pp. 161-163, June 2000 / 2000-06-05

Network node functions, such as QoS or the security functions of routers, are becoming increasingly complex, so programs, not only configuration parameters, are required to control network nodes. In a policy-based network, a policy is defined at a policy server as a set of rules that deployed at network nodes where it must be translated into an executable program or parameters. Thus, a policy must be represented by a form in which the syntax and semantics are clearly defined, and which can be mechanically translated into an executable program. This is possible if the policy is written in an appropriate rule-based programming language. This paper describes such a language in which functions required for DiffServ can be specified for the interface between a policy server and network nodes. In this language, a policy rule can be composed using predefined primitive building blocks and control structures.

Rule-based Modular Representation of QoS Policies

Kanada, Y. / 電子情報通信学会 ネットワーキング・アーキテクチャ・ワークショップ 10 周年記念大会, pp. 106-113, IEICE, 2000 / 2000-02-01

To realize internet-protocol-based QoS-assured networks, using differentiated services under policy-based networking is a promising approach. A QoS policy server must work in multi-vendor environment. To use standard protocol, such as COPS or SNMP, between the policy server and routers is not sufficient, but also to define and to standardize high-level syntax and semantics, i.e., a language, is required for interoperability. This paper describes the outline of a rule-based language for this purpose. Policy rules can be defined in the policy server and can be deployed to routers or router proxies using this language through an appropriate protocol such as COPS, SNMP, or IIOP. The language consists of several types of rules, i.e., matching, policing (or metering), marking, discarding, and scheduling types, and linkage labels that connects rules. A MIB and/or PIB that simulates the language is also explained in this paper. The language will be implemented in near future.

SNMP-based QoS Programming Interface MIB for Routers

Kanada, Y., Ikezawa, M., Miyake, S., Atarashi, Y. / Internet Draft, draft-kanada-diffserv-qospifmib-00.txt, November 1999 / 1999-11-07

This document describes a QoS PIF MIB (Quality-of-Service Programming-Interface Management-Information-Base) to be used as an SNMP-based programming interface for routers. This MIB is intended to be a programming interface for router QoS functions, especially DiffServ-related [RFC2475] functions including packet scheduling (queuing), dropping, and metering that must be modular and concisely described. Traffic-conditioning rules and metering rules for DiffServ-related functions are defined modularly by using "virtual flow labels" and exclusive conditions in rules, and new classifications for packet-scheduling and packet-dropping functions are introduced. This document focuses on satisfying the requirements on programming interfaces or programming languages for router control. Thus, the focus is different from that of DiffServ MIB [DSMIB] or QoS PIB [QoSPIB].

A Method of Geographical Name Extraction from Japanese Text for Thematic Geographical Search

Kanada, Y. / 18th International Conference on Information and Knowledge Management (CIKM'99), pp. 46-54, November 1999 / 1999-11-02

A text retrieval method called the thematic geographical search method has been developed and applied to a Japanese encyclopedia called the World Encyclopedia. In this method, the user specifies a search theme using free words, then obtains a sorted list of excerpts and references to encyclopedia sentences that contain geographical names. Using this list, the user can open maps that indicate the location of the names. To generate an index of names for this searching, a method of geographical name extraction has been developed. In this method, geographical names are extracted, matched to names in a geographical name database, and identified. Geographical names, however, often have several types of ambiguities. Ambiguities are resolved using context analysis and several other techniques. As a result, the precision of extracted names is more than 96% on average. This method depends on features of the Japanese language, but the strategy and most of the techniques can be applied to texts in English or other languages.

Methods of Extracting Year References for Chronological-table-generating Text Searching

Kanada, Y. / International Symposium on Digital Library 1999, pp. 135-142, 1999 / 1999-09-28

A method of extracting year references for a textual information retrieval method called the thematic chronological-table search method is explained in this paper. This search method generates an index by extracting and collecting year references from a text collection. The resulting index and a full-text index are used for searching statements that contain year references and search words. The results are displayed in the form of a chronological table with hyperlinks to the original text. Seven forms of year or century references are extracted and normalized using string matching patterns. The extraction error rate is reduced by using both local and nonlocal contexts. If the lower two digits of a Gregorian year, which matches a form, occurs, it is normalized by supplementing the upper digits using the non-local context. This method has been applied to a Japanese encyclopedia. An evaluation shows the precision of extraction to be higher than 99% in most cases.

検索結果を地域で整理する百科事典テキスト検索のための地名情報抽出法

Kanada, Y. / 情報処理学会 自然言語処理研究会報告 99-NL-132-2, 1999 / 1999-09-01

A text retrieval method called the thematic mapping search method has been developed for Japanese texts. In this method, the user specifies a search theme using free words, then obtains a sorted list of excerpts and hyperlinks to sentences that contain geographical names. Using this list, the user can open maps that indicate the location of the names. To generate an index of names for this searching, a method of geographical name extraction has been developed. In this method, geographical names are extracted, matched to names in a geographical name database, and identified. Geographical names, however, often have several types of ambiguities. Ambiguities are resolved using context analysis and several other techniques. As a result, the precision of extracted names is more than 96% on average when applied to the World Encyclopedia. The rules for information extraction depends on features of the Japanese language, but the strategy and most of the techniques can be applied to texts in English or other languages.

「ネットで百科」 における 「テーマ地図検索」 の機能と実装法

Kanada, Y., Yamazaki, M., Sawada, M., Hirano, Y., Fujii, Y. / 情報処理学会第 59 回全国大会，3P-9, 1999 / 1999-09-01

In the member's only network called "Net-de-hyakka", a service called the thematic mapping search, in which results of encyclopedia text search is ordered along a geographical axis, is offered. In this search, the statements are searched and sorted by geographical names that occur in the text. A map of one of the geographical names can also be opened. The function and implementation method of this search are summarized here.

"Active Edge" 基本アーキテクチャの提案

生澤 満, 吉澤 聡, 三村 到, 金田 泰, 大槻 兼市, 年 通信 / 電子情報通信学会 1999 年 通信ソサイエティ大会，SB-6-4, 1999 / 1999-08-16

百科事典から動的に年表を生成するテキスト検索法のための年代情報の抽出法と表現法

Kanada, Y. / 情報処理学会 情報学基礎研究会報告 99-FI-? / 1999-06-01

A method of textual information retrieval, which is called the thematic chronological-table search method, has been developed. In this method, an index is generated by extracting and collecting year references from a text collection, the index and a statement-by-statement full-text index are used for searching for year references and search words when the user inputs the words, and the result items are sorted by year and displayed. The result item contains a year reference, a sentence that contains the year, and a hyperlink to the original text. In this paper, the method of information extraction in the thematic chronological-table searching is explained. This method has been applied to a Japanese encyclopedia. An evaluation shows the precision of extraction is higher than 99% in most cases. An efficient and less error-prone data representation for year expression that may contain several units such as century, year, month, day, and so on, are also explained.

会員ネットワーク「ネットで百科」の概要と実現法

澤田 瑞穂, 山崎 幹夫, 藤井 泰文, 西岡 真吾, 高野 明彦, 金田 泰 / 情報処理学会第 58 回全国大会，1J-1, 1999 / 1999-03-09

「ネットで百科」 における 「テーマ年表検索」 の機能と実装法

Kanada, Y., Hirano, Y., Sawada, M., Yamazaki, M., Fujii, Y. / 情報処理学会第 58 回全国大会，1J-3, 1999 / 1999-03-01

Vector Compiler and Its Algorithms

Kanada, Y. / 数理解析研究所講究録, 京都大学, 1999 / 1999-02-15

細粒度全文検索法の開発

金田 泰 / 未出版, 1998 / 1998-12-01

従来のテキスト検索は，通常，文書を単位としていた． しかし，ユーザがもとめるのは文書そのものではなく，膨大な文書集合から短時間で必要な 《情報》 を検索することである． そこで，文書中での検索情報の存在場所へのハイパーリンクやその周辺からの抜粋が表示でき，文書中の複数の話題をくべつして全文検索できる 「細粒度検索法」 を開発した． この報告では，テキストを原子というこまかい単位で検索する細粒度検索のモデルを記述し，従来の全文検索エンジンをそのまま，または一部だけ改造して実現できる 2 方法を説明・比較し，試作評価によって従来法よりユーザの負荷を低減できることをしめした．

軸づけ検索法 -- 文書からの抜粋を抽出・整理して出力する全文検索法

Kanada, Y. / 情報処理学会 情報学基礎研究会報告 98-FI-50-4, pp. 25-32, 1998 / 1998-11-01

A full-text search method, which is called an axis-specified search method, is proposed. Excerpts are extracted from documents and ordered by using this method. The user selects an axis, such as year, area or quantity, from a menu, in addition to typing strings to be searched. Then, excerpts related to the axis and strings, and hyperlinks to the original sentences are ordered along the axis and displayed. Even if the number of results is very large, the user can easily survey them, because they are well structured. This method has been applied to an encyclopedia and a newspaper articles. In these applications, distributed descriptions that were related to each other could be gathered, and the user could discover their relationships from the results. For example, by specifying "basin" for a search string and "area" (m2) for an axis, descriptions of the world's largest rivers were extracted from the encyclopedia and sorted according to their basin areas.

Axis-specified Search: A Fine-grained Full-text Search Method for Gathering and Structuring Excerpts

Kanada, Y. / 3rd ACM Conference on Digital Libraries, pp. 108-117, 1998 / 1998-06-27

A text search method, which is called an axis-specified search method, is proposed. This method is suitable for full-text searches of a large-scale text collection. In this method, in addition to specifying search strings, the user selects an axis from a predefined set. The system outputs excerpts and hyper-links that are ordered along the axis. The search strings express the specific subject of the search, and the axis specifies a general-purpose method of ordering results. Short sub-topics, which cannot be easily caught by statistical methods, are effectively gathered from the text collection. The user can get satisfactory results using a simple search string. Even if the number of results is very large, the user can easily survey them, because they are well structured. This method has been applied to an electronic encyclopedia and a newspaper database. In these applications, distributed descriptions that were related to each other could be gathered, and the user could discover their relationships from the results. For example, by specifying "semiconductor" for a search string and "year" for an axis, a table listing seven decades of semiconductor-related topics sorted by year was generated from newspaper issues published over a single year. By specifying "basin" for a search string and "area" (m2) for an axis, descriptions of the world's largest rivers were extracted from the encyclopedia and sorted according to their basin areas.

記憶装置・入出力装置

Kanada, Y. / 「記憶装置」，「入出力装置」 の項目，世界大百科事典，平凡社. / 1998-01-01

Web Pages That Reproduce Themselves by JavaScript

Kanada, Y. / ACM SIGPLAN Notices / 1997-11-01

A JavaScript program in a Web page can clear the page content including the program itself and generate new content. The program can generate exactly the same content including the program itself. This means that a Web page can reproduce itself by JavaScript program that is included in the page. Although exact reproduction is useless, inexact reproduction, which transform part of the content, is usable for more practical purpose. For example, Web pages that change its view from outline mode to detail mode by clicking a button in the page can be implemented using this method. This method can also applicable to other types of documents, such as SGML or XML, if the document may contain self-reproductive program. Another method for reproducing Web pages without reproducing programs is also mentioned. Reproductive Web pages partially but really work on Netscape Navigator.

Web ページを自己再生産する JavaScript プログラム

Kanada, Y. / 情報処理学会 「夏のプログラミング・シンポジウム」, 別冊 (pp. 105-112), 1997-7 / 1997-07-01

A JavaScript program in a Web page can clear the page content including the program itself and generate new content. The program can generate exactly the same content including the program itself. This means that a Web page can reproduce itself by JavaScript program that is included in the page. Although exact reproduction is useless, inexact reproduction, which transform part of the content, is usable for more practical purpose. For example, Web pages that change its view from outline mode to detail mode by clicking a button in the page can be implemented using this method. This method can also applicable to other types of documents, such as SGML or XML, if the document may contain self-reproductive program. Another method for reproducing Web pages without reproducing programs is also mentioned. Reproductive Web pages partially but really work on Netscape Navigator.

Methods of Parallel Processing of Constraint Satisfaction Using CCM -- A Model for Emergent Computation

Kanada, Y. / SIG PPAI, Feb, 1996 / 1996-02-01

Two methods for solving large-scale constraint satisfaction problems using parallel processing are surveyed in the present paper. These methods are based on CCM, which is a model for emergent computation. The number of constraint violations is minimized in these methods. The minimization is performed by optimization of local functions. The computation is stochastic and no global information is used. An annealing method called FAM has been introduced to avoid ``local maxima.'' FAM also works only with local information. Two types of parallel processing of CCM-based constraint satisfaction using FAM has been tested. One is a parallel search and the other is a cooperative search. Our experiments has shown that both methods improve performance almost linearly in large-scale graph coloring problems when the number of processors is ten or so.

Constraint Satisfaction by Parallel Optimization of Local Evaluation Functions with Annealing

Kanada, Y. / 未出版, 1996 / 1996-01-01

A method for solving large-scale constraint satisfaction problems is proposed in the present paper. This method is stochastic (or randomized) and uses local information only, i.e., no global plan is expressed in the program and the computation refer to no global information. This method uses CCM (Chemical Casting Model) as a basis, which is a model for emergent computation proposed by the author. The original CCM-based method minimizes the number of constraint violations not directly but throught optimization of local functions, which are called LODs (local order degrees). This method sometimes falls into a "local maximum." This difficulty is solved by a type of annealing, which we call the frustration accumulation method (FAM). FAM also works only with local information. No global functions is used in FAM, No global parameters such as temperature are used, and global control is thus unnecessary. Experiments show that the performance of this method is not very sensitive to parameter values. This means that parameter tuning is easy. In several problems, the performance is comparable to conventional simulated annealing or GSAT, which are based on global evaluation functions. Because of the nonexistence of global information reference, CCM with FAM can be parallelized very easily. Thus, the performance is improved and is almost linear in certain cases.

Constraint Satisfaction Using Neural Networks with a Local and Autonomous Annealing Technique

Kanada, Y. / 未出版 / 1996-01-01

A method for solving large-scale constraint satisfaction problems using an annealed symmetrically-connected neural network, which is called DSN-FAM, is proposed in the present paper. Some conventional methods, such as Hopfield networks, often fail to find a solution. Some others, such as Boltzmann Machines, take too much time. These difficulties are solved by a type of annealing technique, which we call the frustration accumulation method (FAM). DSN-FAM works only with local information, and no global functions or global parameters such as a temperature are used. DSN-FAM thus works autonomously. That is, no external control is necessary while operating. Experiments show that this method does not fail to find a solution and the execution time is less than one tenth of Boltzmann Machines. The performance can be easily and almost linearly improved by parallel processing using tens of processors.

Combinatorial Problem Solving Using Randomized Dynamic Composition of Production Rules

Kanada, Y. / 1995 Int'l Conference on Evolutionary Computation (ICEC '95), pp. 467-472 / 1995-11-01

The present paper proposes a method of solving combinatorial problems using randomized dynamic rule composition. This method is called CCM* and is based on a computational model called Chemical Casting Model (CCM), which is a rule-based computational model for emergent computation. CCM was proposed by the author toward solving dynamic, open and incompletely specified problems using a few simple rules and evaluation functions. By composing a rule from a given production rule dynamically and randomly, CCM* makes it possible to escape from local maxima, which cannot be escaped from by applying the original rule. This method is compared with the original CCM and another extended version of CCM, i.e., CCM with simulated annealing. 0-1 integer programming problems are solved using these methods. Our experiments show that CCM* performs much better than both the original and annealed CCM. In addi-tion, suboptimal solutions can be found in less time than a branch-and-bound method.

Combinatorial Problem Solving Using Randomized Dynamic Tunneling on A Production System

Kanada, Y. / IEEE Systems, Man and Cybernetics '95 / 1995-10-01

Levy and Montalvo, Yao, and Shima individually pro-posed tunneling algorithms. The tunneling algorithms employ analogy to tunnel effect in physics, and are used to optimize continuous systems. The present paper proposes a method of solving combinatorial problems using a type of randomized dynamic tunneling technique. This method is based on a computational model called CCM*. CCM* is an extended version of the Chemical Casting Model (CCM). CCM was proposed by the author toward developing a method of solving open and incompletely-specified problems that may change while being solved, using self-organizing computation. The 0-1 integer programming problem is solved using CCM* with a very simple rule and an evaluation function. CCM* allows us to escape from local maxima by composing the rule dynamically and randomly. This cannot be done by using the original production rule as is. Our experiments show that approximate solutions can be found more rapidly by CCM* than by using a branch-and-bound method in the case of 0-1 integer programming.

局所情報によるアニーリングをつかった大規模制約充足とその並列処理 -- 創発的計算のためのモデル CCM の応用 --

Kanada, Y. / SWoPP '95 (情報処理学会人工知能研究会), AI95-16, pp. 17-24, 1995 / 1995-08-01

A method for solving large-scale constraint satisfaction problems based on CCM (Chemical Casting Model), which is a model for emergent computation, is proposed in this report. A parallelized version of this method is also shown. Large-scale problems could not be solved using CCM. However, this report shows that, by introducing a method of annealing called FAM (Frustration Accumulation Method) and by adjusting the parameters appropriately, several large-scale graph coloring problems has become solvable with spending the same order of time as GSAT or simulated annealing by sequential processing using CCM. This report also shows that this method can easily be parallelized with restricted amount of mutual exclusion. The performance is almost proportional to the number of processors under certain conditions.

Fuzzy Constraint Satisfaction Using CCM -- A Local Information Based Computation Model

Kanada, K. / Fuzz-IEEE/IFES '95, pp. 2319-2326, 1995 / 1995-06-01

A method of solving fuzzy constraint satisfaction problems defined by Ruttkay is shown in the present paper. This method is based on CCM, which is a computation model for emergent computation or for locality-based problem solving. CCM is a type of production system. It works stochastically, or randomly, and works with evaluation functions that are computed only with local information. CCM has been applied to constraint satisfaction problems (CSPs). Binary-valued evaluation functions, each of which indicates whether a constraint is satisfied, are used. If the values of evaluation functions are extended to real values, fuzzy CSPs can be expressed in CCM, and solved using a technique similar to GSAT or annealing. This method is applied to a fuzzy graph coloring problem, and the performance is evaluated. This method can also be applied to an open and dynamical fuzzy/non-fuzzy CSPs, in which data and constraints are changing dynamically or coming from or going to the outside of the system.

Parallel Processing Method of Local-Information-Based Combinatorial Problem Solving Based on Implicit Stochastic Divide-and-Conquer

Kanada, Y. / 未出版, 1995 / 1995-01-01

A method of solving combinatorial problems, such as the N queens problem or graph coloring problems using independent parallel processes, is proposed in the present paper. This method is stochastic (or randomized). Problems are decomposed for parallel processing implicitly and stochastically by this method. This method is based on CCM, which is a computational model proposed by the author. A program consists of production rules and local evaluation functions in CCM. Each process uses the same set of rules and functions, and it may use the same set of initial data in this method. However, the performance is approximately in proportion to the number of processors in average in certain cases. The theoretical reason of this linear acceleration is explained, and several results of experiments, some of which was successful but others were not, are also shown.

化学反応系とのアナロジーにもとづく開放的で複雑な計算のためのモデル CCM -- その連動式ニューラルネットとの関係について --

Kanada, Y. / 日本神経回路学会第 5 回全国大会, pp. 36-39, 1994 / 1994-12-01

The basics of CCM (chemical casting model), which is a computation model for emergent computation, is explained, and an extension of CCM, i.e., dynamical composition of rules, is described. The relation between the extended CCM and neural networks, especially the neural networks with linked state transition, is mentioned, and the importance of designing good concrete dynamics is also mentioned.

創発的計算のためのモデル CCM による制約充足問題などの独立並列処理法

Kanada, Y. / 情報処理学会 第 49 回全国大会, pp. 4-321 - 322, 1994 / 1994-10-01

CCM (Chemical Casting Model) は，創発的計算にもとづく問題解決法の確立を めざして開発した，非決定的 (ランダム) な計算のモデルである． この研究で は，局所的・部分的な情報だけをつかった，たえず変化する環境のもとでのひ らかれた計算をめざしている． この報告では， CCM にもとづく制約充足問題な どのひとつの並列処理法についてのべる． CCM にもとづく計算においては計算 時間がほぼ指数分布にしたがうばあいがあり，そのときは独立な並列処理に よってプロセッサ台数にほぼ比例する性能向上が期待できることがわかった．

創発的計算のための言語 SOOC: その特徴と実装 -- 魔方陣を例題として --

Kanada, Y. / 情報処理学会記号処理研究会, 94-SYM-75-5, pp. 31-38, 1994 / 1994-09-01

たえず変化する環境に対してひらかれた創発的計算にもとづく問題解決法の確立をめざして， 著者は CCM という計算モデルを提案している． CCM は局所的な情報だけで計算される評価 関数をともなう，ランダムに動作する一種のプロダクション・システムである． その実験を おこなうために計算言語 SOOC-94 とその処理系を開発し使用している． ここでは SOOC-94 の特徴と逐次計算機の Lisp 上の実装について，魔方陣の問題を例として説明する． この言語 の特徴としては，規則適用時に評価関数の自動計算や局所的な自動バックトラックをするこ と，規則の両辺におけるパタンの構文がほぼ統一されていること，規則の適用順序に関する 2 種類のスケジューリング戦略とくにランダム戦略の存在，データ (構造体) の要素と して複数の同名の要素の存在をゆるしていることなどがある．

SOOC-94: An Experimental Language toward Building Real-World Computing Systems

Kanada, Y. / 未出版, 1994 / 1994-09-01

Today's computer applications often require on-line input and output and sometimes requires change of computation methods while processing complex tasks. In future, they will probably be required to change even the objectives of computation. Such a new style of information processing is called real-world computing in the present paper. Real-world computing requires computation languages to work without fixed sequence of control nor fixed data flow, to work without a whole plan of computation, to be always open to environment at any time, to have possibility of distributed and parallel processing, to have possibility to respond to nondeterministic actions, and so on. Because today's programming languages are considered not to satisfy these requirements, a new computation model called CCM (chemical casting model) and a language called SOOC-94, which partially satisfies the requirements, are developed as the first step. Computation is regarded as biased random walk in CCM. The random walk is realized by a randomly acting forward-chaining production system, and the bias is realized by locally computed evaluation functions in SOOC-94. I have developed a preliminary version of compiler and interpreter, and analyzed the computation processes and results of graph coloring problems for example.

創発的計算のためのモデル CCM による問題解決法における局所性の制御法

Kanada, Y. / SWoPP '94 (情報処理学会人工知能研究会), 94-AI-95-4, pp. 29-38, 1994 / 1994-08-01

CCM (Chemical Casting Model) is a model of nondeterministic, or random, computation. CCM is developed toward establishing a problem solving methodology based on emergent computation, which is open to continually varying environment. Computation in CCM is based on local information. However, a solution cannot be found if the locality is at the limit. Thus, the locality of computation, especially computation of the evaluation functions, must be controlled properly, and the locality in the search space must be controlled properly not to fall into local optima. Four methods of controlling locality are shown in this report. They are addition or removal of catalysts, composition of reaction rules (or tunneling), simulated annealing (SA) and frustration accumulation method (FAM). We found that catalysts and FAM are effective in constraint satisfaction, but that the performance is worse than conventional methods when only using these methods in a case. We also found that tunneling, or dynamical composition of reaction rules, is effective in optimization.

The Effects of Randomness in Asynchronous 1D Cellular Automata

Kanada, Y. / Artificial Life IV, Poster, 1994 / 1994-07-01

Cellular automata are used as models of emergent computation and artificial life. They are usually simulated under synchronous and deterministic conditions. Thus, they are evolved without existence of noise, i.e., fluctuation or randomness. However, noise is unavoidable in real world. The objective of the present paper is to show the following two effects and several other effects caused by asynchronism or synchronism and by existence or nonexistence of randomness in the computation order in one-dimensional asynchronous cellular automata (1D-ACA) experimentally. One major effect is that certain properties of two-neighbor 1D-ACA are fully expressed in their patterns if certain level of randomness exists, though they are only partially expressed if no randomness exists. The patterns generated by 1D-ACA may have characteristics, such as mortality of domains of 1's or splitting domains of 0Us into two. These characteristics, which are coded in the RchromosomeS of the automata, i.e., the look-up table, are fully expressed only when the computation order is random. The other major effect is that phantom phenomena, which almost never occurs in real world, sometimes occur when there is no noise. The characteristics of patterns generated by several 1D-ACA are drastically changed from uniform patterns to patterns with multiple or chaotic phases when only low level of noise is added.

創発的計算のためのモデル CCM による動的なグラフ彩色

Kanada, Y. / 人工知能学会並列人工知能研究会, SIG-PPAI-9401, pp. 7-12, 1994 / 1994-04-01

Real world computing systems are complex systems that is open to the continually varying environment. Conventional software development methods inherently cannot deal such situations. CCM (Chemical Casting Model) is a model of nondeterministic, or random, computation, which is based on local information. CCM is developed toward establishing a software development methodology based on emergent computation. CCM is a production system with locally computed evaluation functions. A method of coloring vertices of dynamically changing graphs, or a method of radio-wave assignments to moving stations, by using SOOC -- a CCM-based computation language, is explained, and the results of experiments are shown in the present report. Dynamic coloring can be performed using the same production rule and evaluation function as static coloring, and the results can be evaluated using basically the same method and tools.

プロダクション規則の合成による記号的ランダム・トンネリング -- 計算モデル CCM* による制約充足と最適化 --

Kanada, Y. / 計測自動制御学会第 14 回システム工学分科会研究会 "組合せ問題とスケジューリング問題の新解法,"45-52, 1994 / 1994-04-01

Stochastic Problem Solving by Local Computation based on Self-organization Paradigm

Kanada, Y., Hirokawa, M. / 27th Hawaii International Conference on System Sciences (HICSS-27), 82-91, 1994 / 1994-01-01

We are developing a new problem-solving methodology based on a self-organization paradigm. To realize our future goal of self-organizing computational systems, we have to study computation based on local information and its emergent behavior, which are considered essential in self-organizing systems. This paper presents a stochastic (or nondeterministic) problem solving method using local operations and local evaluation functions. Several constraint satisfaction problems are solved and approximate solutions of several optimization problem are found by this method in polynomial order time in average.

プロダクション規則と局所評価関数にもとづく計算モデル CCM による各種のソート法

Kanada, Y. / 情報処理学会記号処理研究会, 93-SYM-71-5, pp. 33-40, 1993 / 1993-11-01

著者は，局所情報だけで計算されるプロダクション規則と評価関数とを要素とする確 率的な計算モデル 「化学的キャスティング・モデル (CCM)」 とそれにもとづく計算言語 SOOC を提案している． このモデルは仕様も明確にかきくだせない開放系の問題に 適用するために開発したものだが，古典的な問題への適用実験も重要だとかんがえて いる． そこでこの報告では CCM をソートに適用し，あたらしいソート法をしめすと ともに，従来の挿入ソート，交換ソートなどにもとづくソート法をしめす． また，あ わせてそれらの実験結果をしめす． この方法では，唯一のプロダクション規則と唯一 の評価関数をあたえるだけで，局所情報の参照だけにもとづいてソートをおこなうこ とができる． また，局所情報だけをつかうことによって生じる興味ぶかい現象につい ても言及する．

プロダクション規則と局所評価関数にもとづく計算モデル CCM -- その拡張と 0-1 整数計画問題への適用 --

Kanada, Y. / 情報処理学会第 47 回全国大会, pp. 1-99-100, 1993 / 1993-10-01

報告者は局所的部分的な情報にもとづく自己組織的な計算をめざして， 化学的キャスティング・モデル (CCM) という計算モデルを提案している． CCM は化学反応系 とのアナロジーをつかい，プロダクション・システムにもとづく計算モデルであ る．CCM の特徴は，適用対象データに関する局所的な評価関数によってプロダク ション規則の適用が制御される，非決定的あるいは確率的に動作する，手続き的な 解法よりはるかに単純なプログラムで問題がとけるなどである． これまでに N ク ウィーン問題，彩色問題，巡回セールスマン問題などへの CCM の適用を試行した が，ここではそれを拡張して 0-1 整数計画問題に適用した結果を報告する．

化学反応系とのアナロジーにもとづく自己組織的情報処理のためのモデル CCM

Kanada, Y. / 長期研究会 「複雑系 2」 発表報告 (A4, 1 枚) / 1993-08-01

この研究はコンピュータ上で自己組織的計算，すなわち局所的・部分的 (不完全) な 情報だけをあたえて，のぞみの大域的な構造をつくりあげる，創発的 (emergent) な 情報処理法の実現をめざしている． CCM にもとづいて，局所的な情報から彩色問題な どの問題解決ができる． CCM にもとづく制約充足問題をとくシステムは，大域秩序度 の時間変化，触媒の作用などにおいて興味ぶかい動特性をしめすことがわかった．

プロダクション規則と局所評価関数にもとづく計算モデル CCM による問題解決法の特徴

Kanada, Y. / SWoPP '93 (情報処理学会人工知能研究会), 93-AI-89-2, pp. 11-20, 1993 / 1993-08-01

制約充足や最適化などの問題解決は解の探索としてとらえられる． 人工知能やオペ レーションズ・リサーチなどにおける従来の解探索法においては，バックトラックを つかって木構造の探索空間を網羅的・系統的に探索することが基本となっている． 著 者は分散・並列的に作用するプロダクション規則と局所評価関数にもとづく計算モデル CCM (化学的キャスティング・モデル) を提案しているが，CCM による解探索は， 評価関数によってバイアスをかけながら探索空間上を酔歩 (random walk) すること だとみなせる． この方法の特徴は，木ではなく強連結なグラフ上を探索すること，可 逆で対称性がある規則を使用すること，規則がふくむ触媒なるものを加減したり規則 を合成したりすることによってバイアスのつよさや規則の局所度がかえられることな どである．

プロダクション規則と局所評価関数による制約充足問題の解法

Kanada, Y., Hirokawa, M. / 情報処理学会記号処理研究会, 93-SYM-68-2, pp. 9-16, 1993 / 1993-03-01

この報告では， CCM にもとづいてある種の制約充足問題をとく方法をしめす． この方 法では決定的かつ手続き的な制約伝搬にはよらずに確率的な手法によって，また非常 に単純な"プログラム" によって N クウィーン問題 や地図の彩色問題などの制約充足 問題を平均すると多項式時間でとくことができる． この報告ではまた，この方法によ る計算の特性すなわち実行時間やその分布などを実測値にもとづいて論じる．

確率過程としての計算 -- 計算過程のマクロ・モデルの必要性とその例 --

Kanada, Y. / 電子情報通信学会コンピューテーション研究会 / ソフトウェアサイエンス研究会, pp. 1-10, 1993 / 1993-03-01

複雑な記号処理をおこなう計算システムは，プログラムを静的に理解することによっ て，あるいはミクロな動作を追っていくことによってそのふるまいを理解することは できない． したがって，それを理解するには計算過程をマクロにみるモデルが必要で ある． 計算過程のマクロ・モデルはまた，計算の自動制御や自己組織的計算の実現の ためにも必要だとかんがえられる． この報告では計算過程のマクロな理論に関する基 礎検討をおこない，確率過程論にもとづくモデル化を提案する． そして，そのひとつ の例として，ミクロ・モデルとしての 化学的キャスティング・モデル (CCM) に対応するマクロ・モデルとしてマルコフ連鎖モデルをしめし，それにもとづいて CCM にもとづくエイト・クウィーン問題の計算過程を分析する． この理論はミクロ・モデル における記号計算とマクロ・モデルにおけるパタン計算との一種の融合をはかってい るということができる．

プロダクション規則と局所評価関数による最適化の方法とその計算過程におけるマクロなふるまい

Kanada, Y. / 第 11 回計測自動制御学会システム工学部会研究会, pp. 27-34, 1993 / 1993-02-01

著者は自己組織的計算のための 「化学的キャスティング・モデル (CCM)」 とそれにも とづく計算言語 SOOC を提案している． このモデルは仕様も明確にかきくだせない開 放系の問題への適用を本来の目的として開発した． しかしこれを仕様が明確な最適化 問題に適用しても，巡回セールスマン問題などの単純な最適化問題のばあい，唯一の プロダクション規則と唯一の評価関数 (局所秩序度という) をあたえるだけで，局所 的な情報の参照だけにもとづいて問題がとけるという利点がある． この報告では CCM にもとづく最適化の例として巡回セールスマン問題をとりあげ，解法と実験結果とを しめす． また，この方法による計算過程におけるマクロなふるまいを理解するため， マルコフ連鎖にもとづくモデルにあてはめた結果をしめす．

マージ型ベクトル演算機構を用いた非数値処理の高速化方式

Torii, S., Kojima, K., Kanada, Y., Sakata, A., Takahashl, M. / 情報処理学会論文誌, Vol. 34, No. 1, pp. 109-119, 1993 / 1993-01-01

本論文では，ベクトルアーキテクチャをマ一ジ演算に拡張した 内蔵データベースプロセッサ (IDP) を用いた非数値処理高速化の 課題と実例を示す． マージ型ベクトル演算は，各オペランドが 独立にインデックスを持つ点に特長がある． そのため，主記憶上に オペランドを置く必要があり，従来のベクトル演算以上に次の点で 性能上の課題がある． (1) 命令の立上りが遅い， (2) キャッシュ等の階層記憶機構への対応，(3) ベクトル化のオーバヘッドの考慮． 3 個の例題におけるベクトル化の 課題と高速化の効果について，具体的な実験結果を報告する． 関係データベースでは，複数の検索条件のある問合せ処理に適用し， 複数のインデックス利用方式により 4 倍の高速化を実現した， ソートユーティリティでは，2 ウェイのマージ命令を用いて マルチウェイのマージをベクトル化し，4 倍高速化の結果を得た． 解探索の N クィーン間題においても，2 倍の高速化を達成できた．

A Method of Vector Processing for Shared Symbolic Data

Kanada, Y. / Parallel Computing, Vol. 19, 1993, pp. 1155-1175 / 1993-01-01

Conventional processing techniques for pipelined vector processors such as the Cray-XMP, or data-parallel computers, such as the Connection Machines, are generally applied only to independent multiple data prcessing. This paper describes a vector processing method for multiple processings including parallel rewriting of dynamic data strutures with shared elements, and for mutiple procesings that may rewrite the same data item multiple times. This method enables vector processing when entering mutiple data items into a hash table, address calculation sorting, and many other algorithms that handle lists, trees, graphs and other types of symbolic data structures. This method is aplied to several algorithms; consequently, the peformance is improved by a fator of ten on a Hitachi S-810.

自己組織系としての計算システム -- ソフトウェア研究への 2 つの提案 --

Kanada, Y. / 夏のプログラミング・シンポジウム報告集, 1992-7 / 1992-07-01

ソフトウェアを開発するのは不完全な人間であり，また今日では人間社会と密に結合 された大規模・複雑な開放系が開発されていることをかんがえると，閉じた "完全な 計画" を要求する従来のソフトウェア開発法や理論にかわる自己組織的な計算システ ムの開発法や理論を構築することが必要である． そこで，この報告では 「プログラム なしの計算をめざそう」，「計算システムを自己組織系としてみよう」 というソフト ウェア研究への 2 つの提案をする． これらの提案の実現に必要なミクロ・モデルと マクロ・モデルについて説明し，前報でしめした計算モデル CCM を前者の例として 位置づけ，後者の例として計算を確率過程としてみるマルコフ連鎖モデルをしめす．

記号処理プログラムのベクトル処理法とその論理型言語プログラムへの適用

金田 泰 / 東京大学大学院工学系研究科情報工学専門課程 博士論文, 1992 / 1992-03-31

コンピュータによる自己組織系のモデルをめざして

Kanada, Y. / 第 33 回プログラミング・シンポジウム報告集, 1992-1 / 1992-01-01

パタン情報処理のよさをとりいれた自己組織的な記号情報処理のための計算モデルで ある化学的プログラミング・モデル (CPM) を提案する． CPM は，局所的に計算される 秩序度関数の値が増加するように動作するプロダクション・システムである． CPM に もとづく言語処理系を作成してかんたんな実験をおこなった． その結果， N クウィー ン問題などのくみあわせ問題の柔軟なプログラムが非常に簡潔に記述でき，非常に効 率的に実行できることがわかった． CPM を発展させれば，人間がもつ不完全性や非合 理性までをもとりこみつつ，分割統治法がうまく適用できない全体性や開放性をもつ 問題をもあつかえるような自己組織系をコンピュータのうえに実現し，それを数理解 析するための一歩となるとかんがえられる．

ベクトル記号処理のためのデータ構造 「マルチ・ベクトル」 とその応用

金田 泰, 菅谷 正弘 / ソフトウェア科学会 8 回大会, 1991 / 1991-07-01

A Method of Vector Processing for Shared Symbolic Data

Kanada, Y. / International Conference on Supercomputing '91, Albuquerque, 1991 / 1991-06-01

The conventional processing techniques for pipelined vector processors such as Cray-XMP, or SIMD parallel processors, such as CM-2 (connection machine), are generally applied only to independent multiple data processing. This paper describes a vector processing method of multiple processings including parallel rewriting of dynamic data structures with shared elements, and of multiple processings that may rewrite the same data element two or more times. This method is called the filtering-overwritten-label method (FOL). FOL enables vector processing of entering multiple data into a hash table, address calculation sorting, and many other algorithms that handle lists, trees, graphs and other types of symbolic data structures. FOL is applied to several symbolic processing algorithms; consequently, the performance is improved by a factor of ten on the Hitachi S-810.

共有部分がある複数データのベクトル処理方法

金田 泰, 菅谷 正弘 / 情報処理学会第 42 回全国大会, 4M-2, 1991 / 1991-03-01

リストのデータ変換にもとづく Prolog プログラムのベクトル処理法とその評価

金田 泰, 菅谷 正弘 / 情報処理学会第 41 回全国大会, 1990 / 1990-03-01

A Vectorization Technique of Hashing and its Application to Several Sorting Algorithms

Kanada, Y. / PARBASE-90, IEEE, pp. 147-151, 1990 / 1990-01-01

This paper presents a vectorized algorithm for entering data into a hash table. A program that enters multiple data could not be executed on vector processors by conventional vectorization techniques because of data dependences. Our method enables execution of multiple data entry by conventional vector processors and improves the performance by a factor of 12.7 when entering 4099 pieces of data on the Hitachi S-810, compared to the normal sequential method. This method is applied to the address calculation sorting and the distribution counting sort, whose main part was unvectorizable by previous techniques. It improves performance by a factor of 12.8 when n = 2^14 on the S-810.

プログラム変換にもとづくリストのベクトル処理方法とそのエイト・クウィーン問題への適用

金田 泰, 菅谷 正弘 / 情報処理学会論文誌, Vol. 30, No. 7, 856-868, 1989 / 1989-07-01

この論文では，ベクトル計算機を使用してリスト処理を高速に 実行するための基本戦略を提案する． この戦略は，Fortran プログラムのベクトル化技法の拡張と考えることができる 「くりかえし構造の交換」 と 「くりかえし構造の一重化」 というプログラム変換技法にもとづいている． 変換結果の プログラムにおいては，複数のリストを要素とするベクトルを 使用する． それらに関する操作をベクトル計算機のリスト・ ベクトル処理機能や数列生成機能などを用いて実現する． 上記の戦略をエイト・クウィーン問題の Prolog プログラムに 適用し，ベクトル計算機 S-810 においてスカラ処理の約 9 倍の実行速度をえた．

Vectorization Techniques for Prolog without Explosion

Kanada, Y., Sugaya, M. / International Joint Conference on Artificial Intelligence '89, pp. 151-156, 1989 / 1989-07-01

This paper describes a technique for executing logic programming languages such as Prolog for the Cray-type vector processors. This technique, which we call the parallel backtracking technique, enables a kind of or-parallel execution without process explosion. The compiled intermediate language code for the parallel backtracking execution is the same as the code presented in our previous paper. The compilation is based on a kind of program transformation called or-vectorization. However, the interpretation of the intermediate code is changed to enable the parallel backtracking execution. An execution simulator and a compiler prototype were developed. We have not yet implemented this technique to our native code execution system, but we expect a performance of eight times or more higher than scalar processing upon implementation.

OR 並列実行のための論理型言語プログラムのベクトル化法

金田 泰, 菅谷 正弘 / 情報処理学会論文誌, Vol. 30, No. 4, pp. 495-506, 1989 / 1989-04-01

ベクトル計算機 (スーパ・コンピュータ) を使用して 論理型言語プログラムを並行処理するための一種の プログラム変換法 (ベクトル化法) を開発した． このベクトル化法は，OR 並列性があり，引数の入出力モードが 確定しているプログラムを対象とする． この方法では， 原始プログラムの論理変数ごとに，それが探索木上の ことなる位置でとる複数の値を各要素とするベクトルを つくり，それをベクトル処理するプログラムを生成する． この方法を N クウィーン問題のプログラムに適用して自動変換し， 生成されたプログラムがただしく動作することを確認すると ともに，ベクトル計算機 S-810 において 2.6 MLIPS という高い実行速度をえた．

A General-Purpose Conjunctive Iterative Control Structure for Prolog

Kanada, Y. / 未出版, 1989 / 1989-01-01

A loop-like control structure without using backtracking, or conjunctive iteration, is expressed using recursion in Prolog. However, recursion is too powerful to express an iteration, which needs more restrictive syntax and semantics. This paper presents a general-purpose iteration predicate do. Predicate do enables a programmer to write most iterations, such as arithmetical iterations, append, member, mapcar or reduce, and so on, more easily and in more readable way, in combination with the extended λ term, which is a concept similar to the λ expression in Lisp. Unification and logical variables in Prolog enables some extensive usage of the control structure compared with those of other programming languages, such as Lisp.

ベクトル計算機のための探索問題の計算法 「並列バックトラック計算法」

Kanada, Y., Kojima, K., Sugaya, M. / 情報処理学会論文誌, Vol. 29, No. 10, pp. 985-994, 1988 / 1988-10-01

この論文では，探索問題に適用することができる，ベクトル計算機むきの あたらしい計算法並列バックトラック計算法をしめす． この方法にしたがって Fortran でプログラムを記述すれば， 数値計算専用とかんがえられていた S810 のようなスーパ・ コンピュータや，M-680H IAP/IDP (内蔵型アレイ・プロセッサ / 内蔵型データベース・プロセッサ)のようなベクトル計算機構を 付加した汎用計算機で，広範囲の探索問題を高速に実行することが できるまたこの方法では，並列度を適切に制御することによって， 必要な記憶量を逐次計算法とひとしいオーダにおさえることができる． この計算法をNクウィーン問題に適用し，つぎのような性能をえた． エイト・クウィーンの全解探索においては S-81O で逐次処理の約 9 倍，M-680H IAP および IDP を使用して約 1.7 倍だった． また，S-810 においては N ≧ 14 のとき単解探索でも逐次処理より 高速になった． これによって並列パックトラック計算法の有効性が たしかめられるとともに，ベクトル計算機 S-810 および M-680H IAP/IDP の記号処理への適用可能性がしめされた． また， 並列バックトラック計算法は，Prolog のような論理型言語の ベクトル計算磯による高速実行の可能性を示唆している．

Vectorization Techniques for Prolog

Kanada, Y., Kojima, K., Sugaya, M. / ACM International Conference on Supercomputing, pp. 539-549, St. Malo, 1988 / 1988-08-01

Several techniques for running Prolog programs on pipelined vector processors, such as the Hitachi S-820 or the Cray-2, are developed. This paper presents an automatic program transformation (vectorization) method of Prolog, which enables a type of or-parallel execution of Prolog programs using vector operations. Performance is evaluated on the Hitachi S-810 using the Eight-Queens Problem. Its vector execution speed is 4.5 MLIPS (18 ms). This is eight or nine times faster than scalar execution. This result confirms the effectiveness of vectorization techniques and applicability of vector prodcessors to Prolog execution and symbol processing applications.

拡張ベクトル演算による非数値処理高速化

鳥居 俊一, 小島 啓二, 金田 泰, 坂田 明治, 吉住 誠一, 高橋 政美 / 高橋 政美; 電子情報通信学会研究報告, DE88-8, pp. 57-64, 1988 / 1988-01-01

Advanced Vectorization Techniques for Supercomputers

Gotou, S., Tanaka, Y., Iwasawa, K., Kanada, Y., Aoyama, A. / Journal of Information Processing, Vol. 11, No. 1, pp. 22-31, 1987 / 1987-11-01

A new FORTRAN 77/HAP compiler for Hitachi's supercomputers S-810 and S-820 has been implemented featuring new compiling techniques to enable users to easily obtain higher performance. The most important element of this compiler is an advanced global data flow analysis method which determines whether vectorization as well as optimization can be applied or not. Also important are powerful program transformation techniques for vectorization and optimization to vectorize more portions of the programs and produce more efficient code. The performance improvement of this new compiler is compared with the performance of the previous compiler. It is also pointed out that these method and techniques can be applicable to other supercomputers as well.

大域配列データフロー解析法

Kanada, Y., Ishida, K., Nunohiro, E. / 情報処理学会論文誌, Vol. 28, No. 6, pp. 567-576, 1987 / 1987-06-01

配列参照どうしのデータ依存関係としてフロー依存，出力依存および 逆依存があり，これらをグラフ化したのがデータ依存グラフである． 配列参照どうしのデーク依存関係は，従来，各配列参照の添字を 比較してその結果から直接もとめていたが，この方法ではプログラムの 制御構造を反映したデータ依存関係をもとめることがむずかしい． 筆者らは，多重ループの添字を解析することができる添字比較法と， 到達定義 (reaching definitions) や露出使用 (exposed uses) を もとめる変数の大域データフロー解析法とをくみあわせることによって， 条件文や多重ループなどの制御構造を反映したデータ依存グラフを もとめる，配列の大域データフロー解析法を開発した． この解析法では，データ依存関係をループ独立依存， ループ運搬依存などに分類することができる． ここで， ループ独立依存とはプログラム中のループ内の文を1回実行する あいだに生じるデータ依存関係のことをいい，ループ運搬依存とは それを 2 回以上実行することによってはじめて生じる データ依存関係のことをいう． この解析法によって， 従来より強力なベクトル化や最適化ができるようになった．

ベクトル計算機による論理型言語プログラムの高速実行をめざして -- 各種 OR ベクトル実行方式の実現と性能 --

Kanada, Y. / 情報処理学会プログラミング言語研究会, PL-87-12, 1987 / 1987-01-01

ベクトル計算機 (スーパ・コンピュータ) による論理型言語プログラムの 高速実行方式の研究の一部として，OR ベクトル実行方式 (一種の OR 並列実行 方式) の研究をおこなっている． OR ベクトル実行方式にはマスク演算方式， インデクス方式，圧縮方式の 3 種類があるが，これらをそれぞれ詳細化し， N クウィーン問題をとくプログラムに適用した． すなわち，原始プログラム を論理型言語による中間語にプログラム変換したのち Fortran と Pascal とに ハンド・コンパイルし，日立 S-810 による実行性能を測定した． その結果， どの方式でも 8 クウィーン全解探索の時間は 20 ms 弱，大型汎用計算機の 8 ～ 9 倍の性能であり，ベクトル計算機における各実行方式の有望性が 確認できた．

FORTRAN 最適化の強化: 多重ループ内の配列多重添字解析方式

石田 和久, 金田 泰 / 情報処理学会第 33 回全国大会, 1986 / 1986-10-01

スーパー・コンピュータによる Prolog の高速実行

Kanada, Y. / 第 26 回プログラミング・シンポジウム報告集, pp. 47-56, 1985 / 1985-01-01

Compiling Algorithms and Techniques for the S-810 Vector Processor

Yasumura, M., Tanaka, Y., Kanada, Y., Aoyama, A. / Int'l Conf. on Parallel Processing, IEEE, pp. 258-290, 1984 / 1984-01-01

ベクトルコンパイラにおける変数のデータフロー解析の方式

Tanaka, Y., Kanada, Y., Yasumura, M. / 情報処理学会第 27 回全国大会, 7P-9, 1983 / 1983-10-01

多パイプライン方式アレイ・プロセッサのレジスタわりあて方式

Kanada, Y., Yasumura, M. / 情報処理学会第 27 回全国大会, 7P-2, 1983 / 1983-10-01

プログラミング言語学をめざして

Kanada, Y. / 東京大学大学院工学系研究科情報工学専門課程 修士論文, 1981 / 1981-03-31

プログラミング言語を，機械のための言語というより，人間がかき，人間がよむための言語 [そして人間と人間とのコミュニケーションのための言語] と認識すれば，その研究はむしろ人文科学に属するものであることがわかる． そして，そこからプログラミング言語を言語学的に研究する可能性がひらけてくる． そして，おなじ認識からプログラミング言語と自然言語を比較研究することの意義がみいだされる． これまでプログラミング言語の言語学的研究は，興味はもたれていても実際におこなわれたことはないようである． したがって，まずその研究の基礎をきずくことが必要だとおもわれた． そこで，プログラミング言語の言語学的な見方をしめし，プログラミング言語のどの部分にどのような研究方法が適用可能であるかをしらべ，そして研究を方向づけることをこころみた． 本論文でのべる 「言語学的な見方」 のなかでもとくに重要なのは，まずプログラミング言語を慣習 (= 「非成文化規則」) をもふくめた体系としてとらえること，つぎにプログラム単位名の意味をその 「抽象」 との関係としてみることである． またプログラミング言語に言語学的方法をあてはめるための検討のなかでは，自然言語との構造上の類似点などを指摘した． そして，「形態論」 から 「意味論」 におよぶ研究分野をいちおう方向づけした． そのなかで重要な (意味論の) 部門のひとつは，プログラミング言語に存在するあいまい性の研究である． 言語学的研究はおもにすでに存在するプログラムを対象とするが，本論文ではそのような系統的研究をおこなうところまでは達していない． しかし，ここから研究のてがかりをえることはできるのではないかとおもう．

P コードを中間コードとする Pascal 処理系の implementation

Kanada, Y. / 第 21 回プログラミング・シンポジウム報告集, pp. 143-152, 1980 / 1980-01-09

従来の， Trunk からつくった 1 パスの Pascal コンパイラには，Trunk が改訂されたときの再移植がむずかしく，また最適化がむずかしいという欠点があった． この問題を解決するためには，適当な中間コードをえらんで，コンパイラを多パスにすればよいが， そのようなコンパイラを Pascal-P を拡張してつくった． この処理系 (の機械依存の部分) は display をもちいる方式をとったが， 非局所変数のないときには，わずかの最適化をすることによって， もともと非局所変数をもたない言語のばあいとおなじ効率を達成できる．

APPLE II BASIC によるテキスト・エディタ BATE

Kanada, Y. / I/O 別冊 システム・プログラム・ライブラリ 1 / 1980-01-01

文字列の形をしたプログラムやデータの編集ができる 「テキスト・エディタ」 を BASIC で書きました． テキスト・エディタは，特に成績処理など大量のデータを扱かうときには大変便利ですから，まだ使っていない方にはぜひ使っていただきたいと思います．

東京大学教育用計算機センターにおける PASCAL について

Kanada, Y. / 教育用計算センター報告 / 1979-06-01

マルチコンピュータのためのプログラム言語 Dihybrid

Kanada, Y. / 東京大学大学院工学部計数工学科 卒業論文, 1979 / 1979-03-31

共有メモリをもたない計算機システムのプログラムを書く場合，処理装置ごとにプログラムをかくのは問題が多い． かといって，全く逐次的なプログラムをコンパイラで書く処理装置にふりわけるのも難しい． この中間にあって，用途に応じたかきかたのできる柔軟さがあり，しかも効率のよい言語とその処理系はできないものだろうか． このような問題に関する考察は，過度に逐次的だった従来のプログラミングのありかたに対する再検討をうながすものでもある． この論文は不完全ながらもこの問題に対する 1 つの解答を与えるものである．