金田の論文

Kanada, Y., 5th Advanced International Conference on Telecommunications (AICT 2009), 2009-5-25. [新型インフルエンザのために発表はキャンセルされた.]

[ English page ]
[ 論文 PDF ファイル ]

要約: 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ 論文 PDF ファイル ]

要約: アプリケーションによる資源要求と NetFlow によってえられる DiffServ クラスごとのトラフィック計測結果の両方にもとづくアドミッション制御法を開発した． この方法を使用したポリシーサーバのプロトタイプを開発し，シミュレートされた音声トラフィックを使用して実験した． その結果，この方法を使用すればひくい計測負荷で帯域使用率をたかめることができ，呼損を減少させられることがわかった． On/off モデルを使用したシミュレーションの結果，興味ぶかいが害をなしうるダイナミクスが観察された． すなわち，このアドミッション制御法においてはパラメタの値によって発振や 100～150 分間にわたる変化，帯域のオーバーシュートなどの現象がおこることがわかった． これらの現象をおさえてアドミッション制御を適切に動作させられるおよそのパラメタ値の範囲をもとめることができた．

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ 論文 PDF ファイル ]

要約: 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

Kanada, Y., 未出版 (2008-4).

[ English page ]
[ 論文 PDF ファイル ]

要約: 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.

金田 泰, 電子情報通信学会 通信ソサイエティ大会, 2007-7.

[ English page ]
[ 論文 PDF ファイル ]

要約: NGN の目標とされている端点間 (end-to-end) QoS 保証を実現するコア網のためのスケーラブルな QoS 技術の開発をめざしている． 2006 年度は次世代バックボーンにおいて有効なポリシーベースのトラフィック制御法の発見を目標として，QoS 保証方式の開発，プロトタイプの開発と評価実験とをおこなった．

開発した方式においては，RSVP や NSLP にちかいプロトコルによって端末からつたえられる QoS 要求をコア網で集約してスケーラブルな端点間 QoS 保証を実現する． 上記のプロトタイプにおいてこの要求はポリシールーティングとアウトソース型のプロトコルによってポリシーサーバにつたえられ，ポリシーサーバが要求をもとにエッジノードにポリシングとマーキングの設定をおこなうとともに，トラフィック量を予測してコアノードのキューを制御する．

研究テーマ紹介: ポリシーにもとづくネットワーキング

金田 泰, 電子情報通信学会 応用音響 (EA) 研究会, EA2007-42, 2007-8.

[ English page ]
[ 論文 PDF ファイル (投稿後改訂版) ]
[ 論文 PDF ファイル (草稿) ]

要約: voiscape は仮想音響空間内を自由に移動しながら会話できるコミュニケーション・メディアである． そのプロトタイプ VPIIQ (Voiscape Prototype 2 Q) を使用して，ネットワーク・ポリシーのちがいによる QoS のちがいがあたえる効果に関する主観評価を実施したところ，音源方向等をあてる位置判定実験において，予想とちがって QoS がひくいときのほうがやや正答率がたかかった． また，位置判定実験においては被験者が移動・回転の操作をしないときよりそれをしたときのほうが正答率がたかかったが，話者判定実験においては逆の結果がえられた．

研究テーマ紹介: voiscape

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

[ English page ]
[ 論文 PDF ファイル ]

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

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ 論文 PDF ファイル ] [ ポスター PDF ファイル ]

要約: 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 distance 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 voiscape prototype called VPII is used for realizing such an environment. 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 participants can virtually walk among them and can selectively listen one voice or hear multiple voices at once.

研究テーマ紹介: voiscape

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

[ English page ]
[ short paper PDF ファイル ] [ ポスター PDF ファイル ] [ 未出版 full paper PDF ファイル ]

要約: 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

金田 泰, 電子情報通信学会 応用音響研究会, 2005-6.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 3D 音響技術によってつくられた仮想的な "音室" 内を移動して相手を選択しつつ 会話ができるコミュニケーション・メディア voiscape を開発している． Voiscape の第 2 のプロトタイプ VPII においては，FIR 法によって低遅延な HRTF フィルタ計算をおこなうとともに，移動可能な範囲としての音室を 音響計算上の部屋とみなし，その壁による初期反射をシミュレートした． この初期反射によって音の頭外定位と距離感の表現を可能にした． また，ユーザの移動を追跡し必要な補間処理をおこなった． これによって，話者識別が容易で，複数の会話コンテクストが共存することができ， また音室内の移動が自然でノイズがすくない音声コミュニケーション環境を実現した．

研究テーマ紹介: voiscape

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

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 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 repre-sented 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.

研究テーマ紹介: voiscape

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

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 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

金田 泰, 情報処理学会 マルチメディア通信と分散処理研究会, 2004-3.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 電話にかわるべき音声コミュニケーション・メディア voiscape の確立をめざし て研究をおこなっている． Voiscape においては 3 次元オーディオ技術によっ てつくられた仮想的な "音の部屋" を使用するが，音声通信と 3 次元音声にく わえて 3 次元グラフィクスを使用するプロトタイプを PC 上に開発した． この プロトタイプにおいては音声のキャプチャと通信のために JMF (Java Media Framework)，3 次元音声 / グラフィクスのために Java 3D を使用した． 開発 前はこれらの API をつなげば必要な基本機能がほぼ実現できるとかんがえてい たが，実際にはこれらを直接つなぐことはできず，3 次元音声のためには Java 3D のインタフェースをとおして OpenAL を使用した． また，プロトタイプにお いては音質劣化や遅延などの問題を容易に解決することができなかったが，試行 をかさねてこれらの問題をほぼ解決した．

研究テーマ紹介: voiscape

金田 泰, 電子情報通信学会 マルチメディアと仮想環境研究会, 2003-10.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 電話にかわるべきコミュニケーション・メディア voiscape の概念を提案する． Voiscape は，3 次元オーディオ技術による仮想的な "音の部屋" をユーザ間で共有し，そのなかを自由に移動してさまざまなひとと会ったり わかれたりしながら多者間のコミュニケーションがおこなえるウェアラブルな メディアである． プレゼンスや周縁的情報の伝達を可能にし，電話におけるような 1 対 1 の会話から従来のメディアではできなかったさまざまなかたちの コミュニケーションまでをカバーすることによって，つながり感・安心感の 共有や暗黙知の共有も実現されるだろう． この論文では voiscape の使用場面や 手順についてのべ，PC 上に開発した voiscape のプロトタイプについてものべる． プロトタイプ上ではユーザは前方の様子を 3 次元グラフィクスによって 確認しながらマウスをつかって部屋内を移動することができる．

研究テーマ紹介: voiscape

金田 泰, 電子情報通信学会 インターネットアーキテクチャ研究会, 2003-10.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 電話にかわるべき音声コミュニケーション・メディアの確立をめざした研究の 一部として，多者間通信が可能な常時接続型コミュニケーショ ン・メディア voiscape のアーキテクチャとプロトタイプを開発した． Voiscape においては 3 次元オーディオ技術によってつくられた仮想的な "音の部屋" を使用する． ユーザがマウスをつかって音の部屋内を移動すると，プレゼンスサーバを介して 部屋内の位置などのプレゼンス情報が部屋内の他のユーザにつたえられる． 相手にちかづいたり相手からとおざかったりすると，あらかじめ端末において 定義されたポリシーにしたがって，SIP を使用して自動的に通信セッションの 開始・終了などの動作がとられる． このポリシーベース・セッション制御に よってプライバシー保護や通信量削減が可能になる． 接続開始を要求する際に 相手からも同時に接続開始を要求されることが頻繁におこりうるので，2 重に接続したり "話し中" になったりせずに接続が確立する方法を くふうしている．

研究テーマ紹介: voiscape

Kanada, Y. and O'Keefe, B. J., Journal of Network and Systems Management, Vol. 11, No. 3, pp. 253-275, 2003.

[ English page ]
[ JNSM 掲載号 Web ページ ] [ 論文 PDF ファイル (草稿) ]

要約: 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 connec-tions 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 con-trol 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 specify-ing 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 de-scribed, and we concluded that there are five advantages of building-block-based policies, i.e., expressibility, uni-form 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

関連リンク: Research Summary: Rule-Based Building-Block Architecture for Policy-based Networking.

金田 泰, 情報処理, vol. 44, No. 2, 2003.

[ English page ]

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

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: This paper proposes a method, called the policy-extension-by-policy method, for quickly and dynamically adding policy classes with new functionality to policy servers and agents. In this method, users can add a new policy class to the policy server by using policy-definition (PD) policies, and they can define a method to translate a policy of the new class and to send to network nodes of different vendors through various types of device interfaces, such as CLI, MIBs, PIBs, APIs or hardware tables, by using policy-embedding (PE) policies. A PE policy also enables translating a policy of an existing class and sending the result to a new type of network node. PE policies contain command templates and methods for filling the templates. A program interpreter is embedded in policy agents to make flexible policy-to-configuration translation possible. A prototype system and example policies, i.e., access control, Diffserv, and VPN policies, were developed.

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

金田 泰, 電子情報通信学会 2002 年総合大会，2002-3.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: (なし)

金田 泰, ブライアン・オキーフ, 電子情報通信学会 情報ネットワーク・ネットワークシステム 合同研究会，2002-3.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: ネットワークのポリシー制御において，Diffserv のようなプログラムし カスタマイズすることが可能なネットワーク機能を表現するために， 複数のポリシーをくみあわせる必要が生じることがある． PolicyXpert というポリシーサーバにおいて，3 種類のポリシーと，ポリシーを接続するための 3 種類の仮想フローラベル (VFL) とを設計・実装した．ポリシーのくみあわせに よって複雑な Diffserv ポリシーが表現可能になる． また，ポリシーをくみあわせる ことにより，DSCP にもとづくサービスクラスのサブクラスの定義が可能になり， サービスポリシーと加入者ポリシーとの分離が可能になっている． しかも， Diffserv ポリシーを慎重に設計したため，単純な Diffserv ポリシーは単純な かたちであらわせるようになった．

研究テーマ紹介: ポリシーにもとづくネットワーキング

注: PolicyXpert は Hewlett Packard 社の商標です．

Kanada, Y. and O'Keefe, B. J., Asia-Pacific Network Operations and Management Symposium 2001 (APNOMS 2001), September 2001, (poster paper, presentation cancelled).

[ English page ]
[ 論文 PDF ファイル ] [ 未出版フルぺーパ PDF file ]

要約: 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

注: OpenView と PolicyXpert は Hewlett Packard 社の商標です． JP1 は日立製作所の商標です．

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

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

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.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ 論文 PDF ファイル ]

要約: ポリシーベース・ネットワークにおいては，高水準の機能あるいはポリシーを 実現するためにしばしば 2 個以上の低水準のポリシーをくみあわせる必要がある． このような部品化されたポリシーをサポートするために，複数のポリシーを モデル化するための 2 つのアーキテクチャを開発した． それらはパイプ結合 アーキテクチャとラベル結合アーキテクチャである． 規則ベースの部品が ポリシーベース・ネットワーク制御にとってすぐれていること，そして ラベル結合アーキテクチャが現在のところはよりよいことがわかった． しかし， また，ネットワーク環境においては非常に重要な並列性という点においては パイプ結合アーキテクチャのほうがすぐれていることがわかった．

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ 論文 PDF ファイル ] [ 日本語版 OHP PDF ファイル ] [ 英語版 OHP PDF ファイル ]

要約: 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.

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ Local textual version ]
[ Slides used in 46th IETF: Configuration Management BOF, Diffserv WG, and RAP WG (not recommended) ]

要約: 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].

研究テーマ紹介: ポリシーにもとづくネットワーキング

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

[ English page ]
[ 論文 PDF ファイル (ACM DL)] [ 論文 PDF ファイル ]

要約: 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.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

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

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 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.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

金田 泰，山崎 幹夫，澤田 瑞穂，平野 義明，藤井 泰文, 情報処理学会第 59 回全国大会，3P-9, 1999, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 会員制ネットワーク 「ネットで百科」 においては，地域を軸として百科事典 テキストの検索結果を整理して表示する 「テーマ地図検索」 のサービスを 実施している． この検索においては，テキストを文単位に検索し，その結果を 文中に出現する地名によってソートして表示する． また，その地名に関する 地図をひらくこともできる． ここではその機能と実現法の概要を説明する．

研究テーマ紹介: 軸づけ検索 (テーマ検索)

P.S. 残念ながら，現在は 「ネットで百科 」 でテーマ検索をすることができなくなってしまいました．

金田 泰, 情報処理学会 自然言語処理研究会報告 99-NL-132-2, 1999, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 「テーマ地図検索」 というテキスト情報検索法を開発した． この検索法において は，ユーザは検索のテーマを自由語入力し，地名をふくむ文の抜粋とその文へのハ イパーリンクのソートされたリストをえることができる． このリストを使用して ユーザはその地名の位置をしめす地図をひらくこともできる． この検索のための 地名インデクスを生成するため，地名抽出法を開発した． この方法においては， 地名を抽出してデータベース中の地名とマッチングし同定する． 地名には数種類 のあいまいさがある． あいまいさは一種の文脈解析や他のいくつかの技法によっ て解決する． その結果，世界大百科事典においては 96% 以上の抽出精度を実現し た． 情報抽出のための規則は日本語の特徴に依存しているが，その戦略は他の言 語にも適用することができる．

研究テーマ紹介: 軸づけ検索 (テーマ検索)

生澤 満, 吉澤 聡, 三村 到, 金田 泰, 大槻 兼市, 電子情報通信学会 1999 年 通信ソサイエティ大会，SB-6-4, 1999, IEICE により出版.

金田 泰, 情報処理学会 情報学基礎研究会報告 99-FI-?, 1999, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 「テーマ年表検索」 というテキスト情報検索法を開発した． この検索法において は，あらかじめ文書集合から年代参照を抽出して年代インデクスを生成し，ユーザ 入力があると年代インデクスと文単位の全文インデクスとから年代参照と入力され た語の出現場所をもとめて結果を年代順に組織化 (ソート) して表示する． 検索結 果は年代参照とそれをふくむ文，もとのテキストへのハイパーリンクをふくんでい る． この報告ではテーマ年表検索における年代情報抽出法について説明する． こ の方法を世界大百科事典に適用して評価した結果，大半のばあいに 99% 以上の抽出 精度がえられた． また，年月日や世紀など，いくつかの単位がまざった年代表記を 効率よくかつすくない誤差でデータ表現する方法について説明する．

研究テーマ紹介: 軸づけ検索 (テーマ検索)

澤田 瑞穂，山崎 幹夫，藤井 泰文，西岡 真吾，高野 明彦，金田 泰, 情報処理学会第 58 回全国大会，1J-1, 1999, IPSJ により出版.

[ 論文 PDF ファイル (NII) ]

金田 泰，山崎 幹夫，澤田 瑞穂，平野 義明，藤井 泰文, 情報処理学会第 58 回全国大会，1J-3, 1999, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: (なし)

研究テーマ紹介: 軸づけ検索 (テーマ検索)

P.S. 残念ながら，現在は 「ネットで百科」 でテーマ検索をすることができなくなってしまいました．

Yasumura Michiaki, Tanaka Yoshikazu, Kanada Yasusi, 数理解析研究所講究録, 1999, IPSJ により出版.

金田 泰, 未出版, 1998.

[ 論文 PDF ファイル ]
[ 論文ポストスクリプト・ファイル ]

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

研究テーマ紹介: 軸づけ検索 (テーマ検索)

金田 泰, 情報処理学会 情報学基礎研究会報告 98-FI-50-4, pp. 25-32, 1998, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 軸づけ検索法という，文書集合からの抜粋情報を抽出し整理する機能をもつ 全文検索法を開発した． この方法では，ユーザが検索語を入力すると同時に 年代，地域，数量などの軸をメニューから選択する．すると，軸と検索語に 関連する部分の抜粋とその原文へのハイパーリンクがその軸にそって 整列出力される． この方法をつかえば，検索結果が膨大でもユーザ要求に あわせて整理されているので，ユーザはそれをサーベイすることができる． この方法を百科事典と新聞記事に応用した結果，分散された関連情報がうまく 収集でき，検索結果のあいだの関係を発見することができることがわかった． たとえば，検索文字列として 「流域」，軸として 「面積」 をあたえると， 百科事典から世界の川の記述を収集し流域面積でソートした結果がえられる．

研究テーマ紹介: 軸づけ検索 (テーマ検索)

Kanada, Y., 3rd ACM Conference on Digital Libraries, pp. 108-117, 1998, (C) Copyright 1998 by ACM.

[ English page ]
[ 論文 PDF ファイル (ACM DL)] [ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 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" (m²) for an axis, descriptions of the world's largest rivers were extracted from the encyclopedia and sorted according to their basin areas.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

「記憶装置」，「入出力装置」 の項目，世界大百科事典，平凡社.

[ English page ]

Kanada, Y., ACM SIGPLAN Notices, Vol. 32, No. 11, pp. 49-56, November, 1997.

[ English page ]
[ 論文 PDF ファイル改訂版 ]
[ 論文 PDF ファイル (オリジナル) ]

要約:
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 ページの自己再生産

金田 泰, 情報処理学会 「夏のプログラミング・シンポジウム」, 別冊 (105-112), 1997-7.

[ English page ]
[ 論文 PDF ファイル ]

要約: Web ページ中の JavaScript プログラムは，そのプログラムじたいをふくむ ページ内容を消去して，あらたにページ内容を生成することができる． JavaScript プログラムはそのプログラムをふくむ正確に同一のページ内容を 生成できる． したがって，Web ページはそこにふくまれる JavaScript プログラムによって自己再生産できる． 正確な再生産はやくにはたたないが， 内容の一部を変化させる "不正確な再生産" は実用的な目的でつかえる． この方法によって，たとえばページ中のボタンをおすことでアウトライン・モード から詳細表示モードに，またその逆に変化させることができる． この方法は， 自己再生産するプログラムを文書がふくむことができるなら，SGML や XML など，HTML 以外の文書にも適用できる． またここではプログラムを再生産せずに Web ページを再生産する方法についてものべる． 自己再生産する Web ページは 部分的にだが Netscape Navigator において実際に動作する．

研究テーマ紹介: Web ページの自己再生産

Kanada, Y., SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996, Published by JSAI.

[ English page ]
[ 論文 PDF ファイル ] [ 論文ポストスクリプト・ファイル]
[ 論文 DVI ファイル (図をのぞく)] [ EPSF 形式の図 : 1, 2, 3, 4, 5, 6, 7, 8 ]

要旨 (英語のみ) : 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.

研究テーマ紹介: CCM: 化学的計算のモデル

Kanada, Y., 未出版, 1996.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト ファイル ]

[ Java による各種の制約充足問題のデモ (それぞれ触媒，規則，フラストレーションをかえてためせます) ]

要旨 (英語のみ): 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.

研究テーマ紹介: CCM: 化学的計算のモデル

Kanada, Y., 未出版, 1996.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト ファイル ]

要旨 (英語のみ): 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.

研究テーマ紹介: CCM: 化学的計算のモデル

Kanada, Y., 1995 Int'l Conference on Evolutionary Computation (ICEC '95), pp. 467-472, (C) Copyright 1995 by IEEE.

[ English page ]
[ 論文 PDF ファイル] [ 論文ポストスクリプト・ファイル]

要旨 (英語のみ) : 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.

研究テーマ紹介: CCM: 化学的計算のモデル

Kanada, Y., IEEE Systems, Man and Cybernetics '95, (C) Copyright 1995 by IEEE.

[ English page ]
[ 論文 PDF ファイル] [ 論文 ポストスクリプト・ファイル]

要旨 (英語のみ) : 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: 化学的計算のモデル

金田 泰, SWoPP '95 (情報処理学会人工知能研究会), AI95-16, 17-24, 1995, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル: なし (変換失敗 !) ] [ 論文 ポストスクリプト・ファイル]

要旨 (英語のみ) : この報告では，創発的計算のためのモデル CCM (化学的キャスティング・モデル) にもとづいて大規模な制約充足問題をとくための方法を提案する． また，その並 列処理の方法をしめす． CCM にもとづく方法ではこれまで大規模な問題をとくこ とができなかったが，FAM (フラストレーション蓄積法) という一種のアニーリン グを導入し，さらにパラメタをうまく調整することによって，大規模なグラフ彩 色問題を GSAT や シミュレーテッド・アニーリングと同程度の計算時間で逐次処理で とくことができるようになった． さらに，かぎられた量の相互排斥だけをつ かって，比較的容易に並列処理できることがわかった． ある条件のもとではほぼ プロセッサ数に比例する性能がえられた．

研究テーマ紹介: CCM: 化学的計算のモデル

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

[ English version ]
[ 論文 PDF ファイル． (C) Copyright 1995 by IEEE]
[ 論文 ポストスクリプト・ファイル． (C) Copyright 1995 by IEEE]

要旨 (英語のみ) : 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.

研究テーマ紹介: CCM: 化学的計算のモデル

Kanada, Y., 未出版, 1995.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト ファイル ]

要旨 (英語のみ): 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: 化学的計算のモデル

金田 泰, 日本神経回路学会第 5 回全国大会, pp. 36-39, 1994, JNNS により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP PDF ファイル: スライド, ハンドアウト ] [ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]

要旨 (英語のみ) : 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: 化学的計算のモデル

金田 泰, 情報処理学会 第 49 回全国大会, pp. 4-321 - 322, 1994, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ] [ OHP PDF ファイル: スライド, ハンドアウト ]

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

研究テーマ紹介: CCM: 化学的計算のモデル

金田 泰, 情報処理学会記号処理研究会, 94-SYM-75-5, pp. 31-38, 1994, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による魔方陣のデモ (SOOC とは無関係です) ]

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

研究テーマ紹介: CCM: 化学的計算のモデル

Kanada, Y., 未出版, 1994.

[ English page ]
[ 論文 PDF ファイル] [ 論文 ポストスクリプト・ファイル]

要旨 (英語のみ): 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: 化学的計算のモデル

金田 泰, SWoPP '94 (情報処理学会人工知能研究会), 94-AI-95-4, pp. 29-38, 1994, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ] [ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による各種の制約充足問題のデモ (それぞれ触媒，規則，フラストレーションをかえてためせます) ]

要旨 : CCM (Chemical Casting Model) は，たえず変化する環境に対してひらかれた創発的計算にもと づく問題解決法の確立をめざして開発した，非決定的 (ランダム) に動作する計算のモデルで ある． CCM においては局所的な情報をつかって計算がおこなうが，局所的な極限においては 解をもとめることはできない． したがって，計算，とくに評価関数の計算の局所性を制御し て，局所最適点におちいらないように探索空間内での局所性を制御する必要がある． この報 告では 4 つの局所性の制御法をしめす． それらは，触媒の加減，反応規則の合成またはトン ネリング，シミュレーテッド・アニーリング (SA)，フラストレーション蓄積法 (FAM) であ る． これらを比較した結果，制約充足のばあいは触媒の加減と FAM が有効だが，これらだ けでは従来法に計算時間のうえでおとるばあいがあることがわかった． また最適化のばあい はトンネリングすなわち反応規則の動的な合成が有効だとわかった．

研究テーマ紹介: CCM: 化学的計算のモデル

Kanada, Y., Artificial Life IV, Poster, 1994.

[ English page ]
[ 論文 PDF ファイル ] [ ポスター ハイパーテキスト版 ]
[ 未出版 拡大版論文 PDF ファイル]

要旨 (英語のみ): 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.

研究テーマ紹介: RACA: ランダムな非同期セル・オートマトン

金田 泰, 人工知能学会並列人工知能研究会, SIG-PPAI-9401, pp. 7-12, 1994, JSAI により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ ポスター ポストスクリプト・ファイル: Part 1, Part 2 ]
[ ポスター PDF ファイル : Part 1, Part 2 ]

[ Java による彩色のデモ (静的な彩色) ]

要旨 : 実世界の計算システムは刻々と変化する環境に対してひらかれた複雑なシステムであり，従来 のソフトウェア開発法では根本的に対処できないとかんがえられる． CCM (Chemical Casting Model) は，創発的計算にもとづくソフトウェア開発法の確立をめざして開発した，局所情報に もとづく非決定的 (ランダム) な計算のモデルである． CCM は局所的に計算される評価関数を ともなうプロダクション・システムである． この報告では，CCM にもとづく計算言語 SOOC による動的に変化するグラフ頂点の彩色 (移動放送局への電波のわりあて) の方法と実験結果と をしめす． SOOC によれば，静的なグラフ彩色とおなじプロダクション規則と評価関数とをつ かうだけで，動的な彩色をおこなうことができ，基本的におなじ方法と道具とをつかって結果 を評価できる．

研究テーマ紹介: CCM: 化学的計算のモデル

金田 泰, 計測自動制御学会第 14 回システム工学分科会研究会 "組合せ問題とスケジューリング問題の新解法," 45-52, 1994, SICE により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル : なし (変換失敗!)]

要旨 : トンネリング・アルゴリズムという連続系のための最適化法を Levy and Montalvo，Yao，島ら が提案しているが，この報告では，くみあわせ問題をとくための，一種のトンネリングをとり いれた方法をしめす． この方法は，問題解決の途中で問題じたいが変化するような動的な問題 の自己組織的な解決をめざして著者が提案している CCM* (拡張された 化学的キャスティング・モデル) という計算モデルにもとづいている． ここではグラフ彩色問題と 0-1 整数計画問題と を例題として，この方法を説明する． CCM* はプロダクション・システムの一種であるが，こ の方法をつかえば，あたえられたプロダクション規則をそのまま適用してもぬけだせない局所 最大点を，そのプロダクション規則を動的かつランダムに合成することによって，ぬけだすこ とができる．

研究テーマ紹介: CCM: 化学的計算のモデル

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

[ English page ]
[ 論文 PDF ファイル, (C) Copyright by IEEE ]
[ 論文 ハイパーテキスト版 (図は現在利用できません) ]
[ 論文 ポストスクリプト・ファイル, (C) Copyright by IEEE ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ] [ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による N クイーン問題とソートのデモ ]

要旨: 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.

Major features of this method are as follows. Problems can be solved using one or a few simple production rules and evaluation functions, both of which work locally, i.e., on a small number of objects. Local maxima of the sum of evaluation function values can sometimes be avoided. Limit cycles of execution can also be avoided. There are two methods for changing the locality of rules. The efficiency of searches and the possibility of falling into local maxima can be controlled by changing the locality.

研究テーマ紹介: CCM: 化学的計算のモデル

金田 泰, 情報処理学会記号処理研究会, 93-SYM-71-5, pp. 33-40, 1993, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java によるソートと N クイーン問題のデモ (ソートは 1 種類だけ)]

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

研究テーマ紹介: CCM: 化学的計算のモデル

金田 泰, 情報処理学会第 47 回全国大会, pp. 1-99-100, 1993.10, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

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

P.S. より具体的にいうと，ここでおこなった CCM の拡張とは，シミュレーテッ ド・アニーリングとプロダクション規則の合成 (いずれも局所最大点におちいるの をふせぐための方法) である．

研究テーマ紹介: CCM: 化学的計算のモデル

金田 泰, 長期研究会 「複雑系 2」 発表報告 (A4, 1 枚), 物性研究, 1994.2.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ ポスター ポストスクリプト・ファイル : ポスター, ハンドアウト ]
[ ポスター PDF ファイル: ポスター, ハンドアウト ]

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

発表は 1993 年 8 月．

研究テーマ紹介: CCM: 化学的計算のモデル

金田 泰, SWoPP '93 (情報処理学会人工知能研究会), 93-AI-89-2, pp. 11-20, 1993, IPSJ により出版.

[ English page ]
[ 論文 3 訂版 PDF ファイル ] [ 論文 3 訂版 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による彩色のデモ ]

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

研究テーマ紹介: CCM: 化学的計算のモデル

金田 泰, 廣川 真男, 情報処理学会記号処理研究会, 93-SYM-68-2, pp. 9-16, 1993, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による N クイーン問題のデモ ]

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

研究テーマ紹介: CCM: 化学的計算のモデル

金田　泰, 電子情報通信学会コンピューテーション研究会 / ソフトウェアサイエンス研究会, COMP92-93, SS92-40, pp. 1-10, 1993, IEICE により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

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

研究テーマ紹介: CCM: 化学的計算のモデル

金田 泰, 第 11 回計測自動制御学会システム工学部会研究会, pp. 27-34, 1993, SICE により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

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

研究テーマ紹介: CCM: 化学的計算のモデル

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

[ English page ]
[ 論文 PDF ファイル (一部フォント不正)]
[ 論文ポストスクリプト・ファイル ]

要旨 (英語のみ): 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.

研究テーマ紹介: 論理 / 記号 ベクトル処理

鳥居 俊一, 小島 啓二, 金田 泰, 坂田 明治, 高橋 政美, 情報処理学会論文誌, Vol. 34, No. 1, pp. 109-119, 1993-1.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

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

研究テーマ紹介: 論理 / 記号 ベクトル処理

金田　泰, 夏のプログラミング・シンポジウム報告集, 1992.7 (原稿は 1992.11), IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ハイパー テキスト版 ]
[ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル ]

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

研究テーマ紹介: CCM: 化学的計算のモデル

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

[ English page ]
[ PDF 版論文の目次 ]

記号処理プログラムのベクトル処理法や論理型言語プログラムの自動ベクトル化 (Cray-1 タイプの計算機へのあてはめ) の方法を開発した．
-- SIMD 型の自動並列化をかんがえるときは，いまでも，ここからえられる ものがあるのではないかとかんがえている．

研究テーマ紹介: 論理 / 記号 ベクトル処理

金田　泰, 第 33 回プログラミング・シンポジウム報告集, 1992.1, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ハイパー テキスト版]
[ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル ] [ OHP PDF ファイル ]

[ Java による N クイーン問題とソートのデモ ]

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

[注: ここで CPM = CCM です.]

研究テーマ紹介: CCM: 化学的計算のモデル

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

[ English page ]
[ この論文の内容は博士論文にふくまれています．]

研究テーマ紹介: 論理 / 記号 ベクトル処理

Kanada, Y., International Conference on Supercomputing '91, Albuquerque, 1991.

[ English page ]
[ 論文 PDF ファイル (ACM DL) ]
[ 論文 PDF ファイル (一部フォント不正)] [ 論文ポストスクリプト・ファイル ]
[ これは 13. の論文のふるい版です．]

[ この論文の内容は博士論文にふくまれています．]

要旨 (英語のみ): 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.

[ English page ]

研究テーマ紹介: 論理 / 記号 ベクトル処理

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

[ English page ]

研究テーマ紹介:
論理 / 記号 ベクトル処理

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

[ English page ]
[ 論文ポストスクリプト・ファイル ]
[ 論文 PDF ファイル ]

要旨 (英語のみ): 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, pp. 856-868, 1989.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

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

研究テーマ紹介: 論理 / 記号 ベクトル処理

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

[ English page ]
[ 論文 PDF ファイル (1.8 MB) ]

要旨 (英語のみ): 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.

研究テーマ紹介: 論理 / 記号 ベクトル処理

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

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]
[ この論文の内容は博士論文にふくまれています．]

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

研究テーマ紹介: 論理 / 記号 ベクトル処理

Kanada, Y., 未出版, 1989.

[ English page ]
[ 論文 PDF ファイル ]

要約: 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.

金田 泰, 小島 啓二, 菅谷 正弘, 情報処理学会論文誌, Vol. 29, No. 10, pp. 985-994, 1988.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

要旨: この論文では，探索問題に適用することができる，ベクトル計算機むきの あたらしい計算法並列バックトラック計算法をしめす． この方法にしたがって 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 のような論理型言語の ベクトル計算磯による高速実行の可能性を示唆している．

研究テーマ紹介: 論理 / 記号 ベクトル処理

Kanada, Y., Kojima, K., and Sugaya, M., ACM International Conference on Supercomputing, 539-549, St. Malo, 1988.

[ English page ]
[ 論文 PDF ファイル (ACM DL) ]

要旨 (英語のみ): 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.

研究テーマ紹介: 論理 / 記号 ベクトル処理

Torii, S., Kojima, K., Kanada, Y., Sakata, A., Yoshizumi, S., and Takahashi, M., 4th Int'l Conf. on Data Engineering, pp. 194-201, 1988.

[ English page ]

研究テーマ紹介:
論理 / 記号 ベクトル処理

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

[ English page ]

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

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

要旨: 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.

研究テーマ紹介: ベクトル / 並列計算機のためのプログラミング言語処理

金田 泰, 石田 和久, 布広 永二, 情報処理学会論文誌, Vol. 28, No. 6, pp. 567-576, 1987.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

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

研究テーマ紹介: ベクトル / 並列計算機のためのプログラミング言語処理

金田 泰, 情報処理学会プログラミング言語研究会, PL-87-12, 1987.

[ English page ]

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

研究テーマ紹介: 論理 / 記号 ベクトル処理

石田 和久, 金田 泰, 情報処理学会第 33 回全国大会, 1986, IPSJ により出版.

金田 泰, 第 26 回プログラミング・シンポジウム報告集, pp. 47-56, 1985.

[ English page ]
[ 論文 PDF ファイル (2 MB) ]

要旨なし．

解説 : 並列計算機やスカラ処理のパイプライン計算機による Prolog の高速実行に 関してはおおくの研究があるが，この論文はいわゆるスーパー・コンピュータ すなわちベクトル型のパイプライン計算機によって論理型言語を高速化する ことをめざした最初の提案である． この論文は方式をしめしただけだが，その後の 研究によって一定の範囲のプログラムに関して，それが実現されている．

研究テーマ紹介: 論理 / 記号 ベクトル処理

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

[ English pge ]
[論文草稿 PDF ファイル]

研究テーマ紹介: ベクトル / 並列計算機のためのプログラミング言語処理

金田 泰, 安村 通晃, 情報処理学会第 27 回全国大会, 7P-2, 1983.

[ English page ]
[ 論文 PDF ファイル ]

田中 義一, 金田 泰, 安村 通晃, 情報処理学会第 27 回全国大会, 7P-9, 1983.

[ English page ]
[ 論文 PDF ファイル ]

金田 泰, 東京大学大学院工学系研究科情報工学専門課程 修士論文, 1981.

[ English page ]
[ 論文 PDF ファイル (6 MB !) ]

研究テーマ紹介: プログラミング言語学

要旨

プログラミング言語を，機械のための言語というより，人間がかき，人間がよむための言語と認識すれば，その研究はむしろ人文科学に属するものであることがわかる． そして，そこからプログラミング言語を言語学的に研究する可能性がひらけてくる． そして，おなじ認識からプログラミング言語と自然言語を比較研究することの意義がみいだされる．

これまでプログラミング言語の言語学的研究は，興味はもたれていても実際におこなわれたことはないようである． したがって，まずその研究の基礎をきずくことが必要だとおもわれた． そこで，プログラミング言語の言語学的な見方をしめし，プログラミング言語のどの部分にどのような研究方法が適用可能であるかをしらべ，そして研究を方向づけることをこころみた．

本論文でのべる 「言語学的な見方」 のなかでもとくに重要なのは，まずプログラミング言語を慣習 (= 「非成文化規則」) をもふくめた体系としてとらえること，つぎにプログラム単位名の意味をその 「抽象」 との関係としてみることである． またプログラミング言語に言語学的方法をあてはめるための検討のなかでは，自然言語との構造上の類似点などを指摘した． そして，「形態論」 から 「意味論」 におよぶ研究分野をいちおう方向づけした． そのなかで重要な (意味論の) 部門のひとつは，プログラミング言語に存在するあいまい性の研究である．

言語学的研究はおもにすでに存在するプログラムを対象とするが，本論文ではそのような系統的研究をおこなうところまでは達していない． しかし，ここから研究のてがかりをえることはできるのではないかとおもう．

目次

1. はじめに
   1. プログラミング言語にかかわる研究の分野
   2. プログラミング言語と自然言語の対照研究の意義
2. プログラミング言語とはどういうものか
   1. プログラミング言語の 3 つの表現
   2. プログラミング言語の規則
      1. 成文化規則と非成文化規則 1
      2. 「非成文化規則」 は存在するか
      3. 成文化規則と非成文化規則 2
      4. 成文化規則の細分
      5. 伝達機能による規則の分類
      6. プログラミング言語の規則と自然言語の規則
      7. 規則の柔軟性
      8. 規則の複雑さについて
      9. 規則にかかわる言語学的研究の課題
   3. プログラミング言語の自立性
      1. 自立性を検討する理由
      2. 非自立性を支持する根拠
      3. 自立性を支持する根拠
      4. 工学的検討
   4. 「意味」のとらえかた
      1. 基本的三角形
      2. 「意味」の定義
   5. 言語の特性
      1. 「自然言語の特性」 A. 伝達機能，B. 記号の恣意性，C. 体系性，D. 記号とメッセージの線条性 (linearity)，E. 単位の離散性 (discreteness)，F. 2 重分節 (double articulation)
      2. プログラミング言語は言語の特性をそなえているか A. 伝達機能，B. 記号の恣意性，C. 体系性，D. 記号とメッセージの線条性，E. 単位の離散性，F. 2 重分節
   6. プログラミング言語のほかの特徴
      1. あいまい性について
      2. 閉鎖性と進化性
      3. プログラミング言語ははなされない
      4. 命名の頻度と語の有効範囲 (scope)
      5. プログラムは「つかわれ」，かきかえられる
   7. プログラミング言語の非言語的部分
      1. 式の性質 A. 非 2 重分節性，B. 非線条性
      2. 非言語的部分の存在意義
   8. プログラミング言語の変化 (variety and change)
3. プログラミング言語学とその研究分野
   1. 個別的研究
      1. 個別的研究の分野
      2. 文法論
      3. 意味論
   2. 比較対照研究
4. 形態論ことはじめ
   1. 記号の分類とその構造
   2. 識別子の分節
   3. 変数名の構造
   4. よびだしの構造
      1. 規定書上の構造
      2. 関数よびだしの構造
      3. 手続きよびだしの構造
      4. 手続きよびだしの構造に関する工学的考察
   5. 識別子の縮約
      1. 識別子のながさの制約と対策
      2. 縮約規則
5. あいまい性の研究
   1. 一般的意味，多義性，同音性
   2. 多義性，同形性の起因
   3. あいまい性の解決の必要性
   4. 多義性，同形性の解決
   5. あいまい性の存在意義
6. むすび
7. 文献目録
8. 謝辞

追記 (2007)

プログラミング言語を (人間の) 言語学的に (すなわち人文科学的に) 解析することをめざした論文である． (プログラミング言語に関しては，言語学的にみて当時と現在とでそれほどおお きな変化はないとかんがえられる． しかし，当時まだひろくつかわれていなかっ たデータを記述するための言語とくに XML が，現在ではひろくつかわれるように なっている． XML を言語学的に解析することでえられるものがあるだろうとおもう.)

金田 泰, 第 21 回プログラミング・シンポジウム報告集, pp. 143-152, 1980.

[ English page ]
[ 論文 PDF ファイル ]

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

研究テーマ紹介: スカラー計算機のためのプログラミング言語処理

T.KY., I/O 別冊 システム・プログラム・ライブラリ 1, pp. 145-156, 1980.

[ English page ]
[ PDF ファイル ]

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

付記: T.KY. は金田がつかったペンネームです． 関連するブログのエントリーがあります．

金田 泰, 教育用計算センター報告, No. 13, pp. 3-25, 1979.

[ English page ]
[ PDF ファイル ]

研究テーマ紹介: スカラー計算機のためのプログラミング言語処理

これは論文ではないが，東大の教育用計算機センターにおいて 1979 年当時つかわれていた Pascal の標準 Pascal とのちがいなどについて書いたものである． 教育用計算機センターにおいてはその後， 金田が開発した Pascal コンパイラが導入されるが，この文章は もとのコンパイラに関するものである．

金田 泰, 東京大学大学院工学部計数工学科 卒業論文, 1979.

[ English page ]
[ 論文 PDF ファイル (8 MB !) ]

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

研究テーマ紹介: ベクトル / 並列計算機のためのプログラミング言語処理

P.S. マルチコンピュータ・システムのためのプログラミング言語を設計し，実装も 検討したが，処理系は完成しなかった． まだ Occam もなかった時代に C. A. R. Hoare の Communicating Sequential Processes に影響されて書いた 卒業論文である．