著者

伊藤愛 追川 修一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.49, no.2, pp.98-112, 2008-03-15

被引用文献数

1

---

これからの組み込みシステムでは,ユーザの選択したアプリケーションを動作させるとともに,安全で効率の良い実行環境を実現する必要がある.その解決策として,VMM は有効な手段である.組み込みシステムでVMM を動作させることによって,資源の効率利用,安全性の向上,信頼性の向上を実現することができる.そのため,マルチコアCPU 指向の軽量VMM として,Gandalf を設計,実装してきた.本論文では,ゲストOS 間のメモリ保護を実現するシャドウページングについて述べる.シャドウページングを利用することで,VMM がゲストOS のメモリ利用を監視することができる.2 方式のシャドウページングを設計し,実装を行った.それぞれの方式について評価実験を行い,ネイティブなLinux やXenLinux との比較した.その結果,Gandalf がXen より軽量に実現できていること,また,割込み応答性に対して軽微な影響で済んでいることが確認できた.While the provision of secure and reliable, yet efficient execution environments is a must for embedded systems, users' desire for using applications of their own choices is rapidly growing. In order to deal with both requirements, VMMs will be an answer. By using VMMs in embedded systems, we can effectively utilize the resources, improve safety and reliability. We designed and implemented a multi-core processor-oriented lightweight VMM, Gandalf. This paper focuses on shadow paging, which enables memory protection among guest OSes. A VMM can monitor the use of memory by guest OSes through shadow paging. We designed and implemented the two models of shadow paging. The results from benchmark experiments show that Gandalf performs better than Xen.

著者

広渕 崇宏 中田 秀基 伊藤 智 関口 智嗣

出版者

情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.3, no.3, pp.248-262, 2010-09-17

被引用文献数

3

---

ポストコピー型の仮想マシン再配置機構は仮想マシンの実行ホストを素早く切り替えられるため,データセンタの運用効率を向上させるうえで有用な技術であると考えられる.しかしながら,今日一般的に利用できるまでには至っていない.先行研究におけるポストコピー型再配置機構は,既存の仮想マシンモニタ(VMM)への変更が大きく,ゲストOSの改変も必要になる点に問題がある.そこで我々は,既存VMMのへ拡張が単純でゲストOSの改変も不要な,新たなポストコピー型ライブマイグレーション機構を提案する.メモリアクセスのトラップ処理とメモリページのコピー処理をVMMの外部で実装することで,VMMへの変更量を抑えながらポストコピー型再配置を実現する.再配置性能を検証するため,SPECweb2005を用いて評価実験を行った.負荷の高いウェブサーバを実行するVMであっても,1秒以内に実行ホストを切り替えることができた.実行ホスト切替え後の性能低下は限定的であった.プレコピー型再配置に比べて,VMのすべての状態を移動する時間も短縮できた.Post-copy-based VM migration is considered a promising technology for next-generation datacenters; memory pages are transferred after a VM restarts at a destination host, thereby minimizing the time of switching the execution host. Post-copy-based migration mechanisms, however, have not yet been available in industry. Prototype implementations in prior work need major modifications to existing virtual machine monitors (VMMs), and also require special software support in guest operating systems. In this paper, we propose a simple and plain implementation of post-copy-based migration, which is implemented as a lightweight extension to KVM. It supports any guest operating systems without their modifications. The RAM of a migrated VM is mapped to a special character device, which transparently transfers memory pages on demand. Experiments were conducted by using the SPECweb2005 benchmark. A running VM with heavily-loaded web servers was successfully relocated to a destination within one second. Temporal performance degradation after relocation was alleviated by pre-caching memory pages. In addition, for memory intensive workloads, our migration mechanism moved all the states of a VM faster than a pre-copy-based migration mechanism.

著者

太田 淳 三輪 忍 中條 拓伯

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.4, no.3, pp.115-132, 2011-05-12

---

Android 端末では,Java プログラムは,Dalvik バイトコードと呼ばれる独自のバイトコードに変換され,VM を介して実行される.VM による実行は時間がかかるため,Java バイトコードを携帯端末で実行する場合は,ハードウェア・アクセラレーションがよく行われる.一方,Dalvik バイトコードの場合は,まだ歴史が浅いため,その高速化に関する研究は十分でない.そこで我々は,携帯端末における Dalvik バイトコード実行の高速化機構として,Dalvik アクセラレータを開発することにした.バイトコードの各オペランドはメモリ上に存在するため,単純にアクセラレータを実装すると,多数のメモリ・アクセスが発生してしまう.この問題に対し,物理レジスタを最大限活用することでメモリ・アクセスを削減する機構を提案する.本機構により,大部分のメモリ・アクセス命令を削減できることが分かった.

著者

薄井 弘之 内山 真郷 伊藤 務 山崎 信行

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.45, no.11, pp.105-118, 2004-10-15

被引用文献数

4

---

分散リアルタイム処理用Responsive Multithreaded ProcessorのプロセッシングユニットであるResponsive Multithreaded Processing Unit (RMT PU) の命令供給機構を設計・実装する.RMT PU は8wayのSimultaneous Multithreading(SMT)方式にリアルタイムシステムの優先度を導入してすべての機能ユニットを設計することで,各スレッドを優先度順に実行し,リアルタイム実行を行う.RMT PUの命令供給機構において,単純に優先度による制御を行うと優先度の低いスレッドが実行される機会が少なくなり,システム全体の性能が低下してしまう.そこで,パイプラインの状況によって低い優先度を持つスレッドを実行することで,高い優先度のスレッドの性能を維持しながら,プロセッサ使用率を向上させる.特に単一スレッドの性能を重視するポリシと,単一スレッドの性能の低下を抑制しつつ,全体の性能に比重を置くポリシの2種類を実装することで様々なデッドラインを持つタスクのスケジューリングを支援する.パイプラインの状況によって対応するスレッドのフェッチを止める方法が最も効果的であり,命令バッファ内命令数や,分岐命令数によるもので最高優先度スレッドの性能低下を1%未満に抑えつつ,全体性能を10%から20%向上できた.また,パイプライン中命令数によってフェッチを止める方法では,全体性能を約100%向上しながら,最高優先度スレッドの性能低下を40%程度に抑えることができた.We design and implement the instruction supply mechanism for Responsive Multithreaded Processing Unit (RMT PU), the processing unit of Responsive Multithreaded Processor for distributed real-time systems. Priority used in real-time systems is introduced into all functional units of the 8way Simultaneous Multithreading (SMT) in RMT PU. Each thread is executed in priority order to realize real-time execution. In the instruction supply mechanism of RMT PU, if control by the priority is performed simply, the opportunity for a thread with a low priority to be executed will decrease and the whole performance will decrease. Then, by selecting the thread which has low priority according to pipelines's situation, the processor utilization is raised without reducing the performance of the thread with the highest priority. We implemented the policy which considers especially performance of the thread with highest priority as important, and the policy which considers the whole performance controlling the fall of the performance of the thread with highest priority. By changing and performing these policy, scheduling tasks which have various deadline are supported. The policy of stopping fetch according to a pipeline's situation is the most effective. By the policy based on the number of the instructions in instruction buffer or the number of branch instructions, whole performance can be improved 20% from 10% suppressing the performance fall of the highest priority thread to less than 1%. By the policy based on the number of the instructions in pipeline, the performance fall of the highest priority thread is able to be suppressed to 40%, doing improvement of a whole performance in 100%.

著者

岩下 武史 美舩健 島崎 眞昭

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.48, no.8, pp.1-10, 2007-05-15

被引用文献数

5

---

マルチグリッド法において,スムージング,補間・制約演算を陽的に行わない新しい方法:陰的マルチグリッド法を提案する.同手法では,マルチグリッド法における各レベルの方程式を統合化し,1つの大きな連立一次方程式として主に前処理付きクリロフ部分空間反復法により解く.その結果,従来のマルチグリッド解法の応用範囲を広げ,様々な前処理手法との併用が可能となる.同手法の基礎概念,実装法を記述し,その有効性について電磁界解析における反復法の性質との類似性から説明する.さらに,差分解析による数値解析において,同手法がコースグリッドコレクションの効果を有し,グリッドサイズによらない収束性を実現していることを示す.This paper proposes a new multigrid method, which is called "Implicit correction multigrid method". In this method, linear systems of equations on all levels in a multigrid method are integrated into one large linear system of equations. When this integrated linear system is solved by using preconditioned iterative solvers, an effect of coarse grid correction is expected to be implicitly involved. Since any preconditioning techniques are used for the integrated linear system, the proposed method can extend application areas of conventional multigrid solvers. This paper describes the basic concept and the implementation way of the implicit correction multigrid method. Furthermore, we explain the effect of the proposed method by introducing a special characteristic of an iterative method observed in an electromagnetic field analysis. Finally, numerical tests based on a finite difference analysis confirm that the proposed method involves an effect of coarse grid correction and attains a convergence rate independent from the grid-size.

著者

吉見 真聡 長名 保範 岩岡 洋 西川 由理 小嶋 利紀 柴田 裕一郎 岩永 直樹 舟橋 啓 広井 賀子 北野 宏明 天野 英晴

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.48, no.3, pp.45-58, 2007-02-15

被引用文献数

4

---

確率モデル生化学シミュレーションアルゴリズム(SSA)は,定義した生化学システムの確率的挙動を厳密に計算できるアルゴリズムとして知られている.しかし,SSA の実行には膨大な計算時間が必要であり,高速な実行環境が求められている.本論文では,高速実行の一手法として,Xilinx 社のFPGA(XC2VP70-5)を用いて,SSA(First Reaction Method)を実行する回路を実装,評価した結果について述べる.高速化は,パイプライン化した演算ユニットを使い,複数スレッドのシミュレーションを同時に実行することで実現する.シミュレータ回路は,中間データをBlockRAM に保持し対象の生化学システムごとの回路再構成を要しない,実用的な構造になっている.ベンチマーク的に定義できる生化学システムTIS,D4S で評価した結果,Xeon 2.80 GHz による実行と比較して,TIS では約83 倍,D4S では約95 倍のスループット向上が可能であることを確認した.This paper discusses an FPGA implementation and evaluation of a Stochastic Simulation Algorithm (SSA) called the First Reaction Method. SSAs are widely known as rigorous methods for simulating the stochastic behaviors of various biochemical systems, but also as CPU-hogging applications due to vast repetition of the algorithm. This work accelerates the execution by achieving high throughput with concurrent simulations of highly utilized pipelined arithmetic units. For upgrading practical utility, the design stores intermediate data in a BlockRAM so that reconfiguration is unnecessary for different target biochemical systems. Benchmark results on an FPGA (Xilinx XC2VP70-5) have shown that the circuit provides throughput of approximately 83 times and 95 times compared to software execution on Xeon 2.80 GHz when it was evaluated with biochemical models called TIS and D4S, respectively.

著者

井上 拓 森山 孝男 小松 秀昭 中谷 登志男

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.47, no.7, pp.105-113, 2006-05-15

---

データを値の順番に並べ直すソート処理は多くのソフトウェアで使用される最も基本的な操作の1 つであり,ソート処理の高速化は多くのワークロードの性能向上に寄与する.ソート処理は基本的な操作であるため,古くから多くのアルゴリズムが提案されているが,近年の高性能な汎用プロセッサのSIMD 命令を用いて高速にソートを行うことのできるアルゴリズムはこれまで提案されていない.そこで本研究ではPowerPC アーキテクチャが持つSIMD 命令セットであるVMX を使用して,並列に処理を行うとともに分岐予測ミスの影響をなくすことで高速にソート処理を行うことのできるアルゴリズムを提案する.このアルゴリズムを実装し,PowerPC 970FX プロセッサ上で評価を行い,クイックソートと比較して最大で5.6 倍の性能向上が得られることを示した.Sorting is one of the most common operations done by computers and used in variety of software. Sorting is a well-studied problem and hence there are many sorting algorithms and implementations available. However there is no sorting algorithm that effectively exploits SIMD execution units of recent general purpose processors. In this paper, we proposed a novel sorting algorithm for VMX instruction set of the PowerPC architecture. This algorithm divides input data in sorting phase and merges them after sort in order to exploit parallelism of the VMX instruction set. Also it removes stall cycles due to conditional branches by replacingthem with vector minimum and vector maximum instructions. We implemented the algorithm and evaluated the performance on the PowerPC 970FX processor. Our results showed that our new algorithm achieved up to 5.6 times higher performance than quicksort.

著者

鈴木 郁真 池内 康樹 津邑公暁 中島 康彦 中島 浩

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.46, no.16, pp.129-143, 2005-12-15

被引用文献数

5

---

遺伝的アルゴリズムにおいて最も処理時間を要する適合度計算に対し,再利用を適用することで高速化する手法を提案し,再利用の有効性を示す.適合度計算の入力となる遺伝子が,前世代で処理された遺伝子と多くの共通部分を持つことから,適合度関数を分割することで再利用の効果を引き出す手法について述べる.GENEsYs を用いて評価した結果,2 点交叉で最大83%,平均27%のサイクル数を削減できた.さらに,関数分割などの改良を施すことにより,最大86%,平均38%までこれが向上した.特に適合度計算に要する時間が長い適合度関数について,再利用の効果がより大きくなることが分かった.This paper describes a speedup technique with computational reuse for the fitness calculation of GA programs. A genotype has many genes in common with its parental genotypes. Therefore, partial results of fitness calculation are reusable. Through the result of an evaluation with GENEsYs, a well-known GA software, we show that the maximum ratio of the cycle reduction reaches 83%, while accomplishing average reduction of 27% with 2-point crossover. Futhermore, dividing fitness procedures raises the maximum ratio to 86% and average ratio to 38%.

著者

中島耕太 佐藤充 久門 耕一 谷口 秀夫

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.48, no.18, pp.69-82, 2007-12-15

被引用文献数

1

---

本論文では,10Gb Ethernet上のRDMA転送機能による仮想マシン移動の設計と評価について述べる.転送時間の削減のために,RDMA転送機能の適用と,NICによる通信処理とCPUによるページのマップ/アンマップ処理のオーバラップ化を図る.また,転送処理が消費するCPU時間の削減のためには,1ページ転送あたりのCPU時間と総転送ページ数を削減する必要がある.仮想マシン上でアプリケーションを動作させたまま転送する場合は,転送処理の間,アプリケーションがページを更新するため,更新ページの再送が生じる.そこで,転送時間の削減により,再送ページ数を削減する.そして,RDMA転送機能の適用により,1ページ転送あたりのCPU時間を削減する.RDMA転送を適用した結果,TCP/IPによる転送時と比較して,アプリケーションが動作している2GBの仮想マシンの転送時間を40.7%削減し6.40 s(336MB/s相当)を達成した.また,転送処理が消費するCPU時間を最大73.6%削減し,仮想マシン上で動作するアプリケーション性能を最大2.68倍に改善した.さらに,オーバラップ化を適用した結果,オーバラップ化非適用時と比較して,転送時間を50.8%削減し3.15s(681MB/s相当)を達成した.また,転送処理が消費するCPU時間を最大11.7%削減し,仮想マシン上で動作するアプリケーション性能を最大6.4%改善した.This paper describes design and evaluation of a virtual machine (VM) migration using RDMA data transfer mechanism over 10Gb Ethernet. In order to reduce elapsed time, we apply RDMA data transfer mechanism and overlap data transfer processing by NIC and page map/unmap processing by CPU. In order to reduce CPU time of VM migration, it is necessary that reduction of CPU time per a page transfer and total number of transfer pages. We apply RDMA to reduce CPU time per a page transfer. And in running application on VM, the reduction of elapsed time reduces total number of transfer pages. By using RDMA data transfer, the migration time of the 2GB VM on which application was running was shorter in 40.7% than using TCP/IP data transfer, and 6.40s (suitable to 336MB/s) was achieved. Moreover, CPU time of VM migration was reduced in 73.6% and the performance of application on VM is improved 2.68 times. In addition, the migration time applied the overlap method was shorter in 50.8% than applied only RDMA, and 3.15s (suitable to 681MB/s) was achieved. CPU time of VM migration was reduced in 11.7% and the performance of application on VM is improved 6.4%.

著者

水上 智雄 長健二朗

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.46, no.12, pp.338-348, 2005-08-15

---

本論文では,ローカルネットワークにおけるサービスディスカバリの技術を用いることにより,VPN各種やSoftEther などとは違うアプローチで,複数のローカルネットワークサービスを連結接続して,リモートネットワークからそれらサービスにアクセスするアーキテクチャモデル「Tunneling with Service Discovery」を提案する.そのアーキテクチャモデルは,サービスディスカバリの連結機能とサービス自体の中継機能から構成される.まず,このモデルでは,サービスディスカバリのリスティング機能を用いて,ローカルネットワークにおけるサービス情報をダイナミックに集約するサーバを用意する.次に,サーバから得るサービス情報を基に,クライアントのローカルホストにサービスをマッピングし,そのサービスをクライアントのローカルネットワークのサービスディスカバリに登録する.これにより,擬似的にほかのローカルネットワークのサービスを,自分のネットワークのサービスとして自動的に利用することが可能になる.このモデルを用いることで,リモートネットワークからVPN でローカルネットワークに接続する場合ではなしえない,1 方向アクセス,マルチプルログイン,多段アクセスが可能になる.また,それにともなったネットワーク構成の変更の必要も生じない.本研究での実装においては,サービスディスカバリの技術としてMulticast DNS(mDNS)を用いて,ローカルネットワークサービス連結接続ソフトウェア「RNSplicer」の開発を行った.このソフトウェアにより,Mac OS X で標準的に利用されるBonjour(旧名Rendezvous)で提供されるローカルネットワークサービスを中継可能にした.In this paper, we propose a new architecture model, Tunneling with Service Discovery, for accessing local network services from a remote network. The model allows to splice local network services from multiple remote networks so that users can transparently access the advertised services as if they were local services. This architecture model consists of splicing networks and relaying services, and is different from the existing remote access technologies such as VPN and SoftEther. In this model, a server makes use of Service Discovery, and dynamically collects and updates the information about available local network services. A client on a remote network talks to the server, obtains the service information, maps these remote services onto its local services, and then, registers the mapped services on its local Service Discovery. Therefore, all hosts on the client's network are able to use the relayed services as pseudo local services. The model also allows One-way Access, Multi-Network Access and Multi-Stage Access without requiring any network reconfiguration. As an implementation of this architeture, we have developed "RNSplicer" that splices local network services provided by Multicast DNS (mDNS). RNSplicer works with all types of services provided by Bonjour (Rendezvous), a standard service discovery technology employed by Mac OS X and Darwin.

著者

成瀬 彰 住元 真司 久門 耕一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.45, no.11, pp.62-70, 2004-10-15

参考文献数

16

被引用文献数

1

---

本論文では,PCクラスタのプロセッサとしてよく使用されるXeonプロセッサ向けのLinpackベンチマーク高速化手法について述べる.特に,Linpackベンチマーク実行時間の大半を占める倍精度行列積(DGEMM)の最適化手法について説明する.最適化はオープンソースの数値演算ライブラリであるATLASをベースに行い,キャッシュ容量,TLBエントリ数,システムバス負荷の均等化を考慮してDGEMMカーネルを作成し,それに合わせてDGEMMカーネル呼び出し部分を変更した.最適化したDGEMMを2.4 GHz Xeonプロセッサを搭載したFujitsu PRIMERGY L250で評価した結果,DGEMMそのものの性能を測定する正方行列積プログラ厶では4.33 GFlops(実行効率:90.2%)を記録した.また,Linpack ベンチマークでは4.13 GFlops(実行効率:86.0%)を記録した.これは従来最速とされていたGOTO BLAS を5%上回る性能である.In this paper, we explain the optimization technique of matrix multiplication (DGEMM) for Xeon processor, that is heavily used in Linpack benchmark. Our optimization technique is based on reducing cache misses and D-TLB misses and averaging FSB (Front Side Bus) loads. We have applied this technique to an open-source numerical library ATLAS. The benchmark results using our DGEMM implementation show better performance than GOTO BLAS that is famous for a fast DGEMM. On a Fujitsu PRIMERGY L250 system equipped with 2.4 GHz Xeon processors, performance of square matrix multiplication program attains 4.33 GFlops (90.2% efficiency) and performance of Linpack benchmark attains 4.13GFlops (86.0% efficiency).

著者

高橋 慎 加藤 和彦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.44, no.11, pp.268-276, 2003-08-15

---

Suffix arrayはテキストの接尾辞のポインタを辞書順に並べ替えたもので,任意の部分文字列を高速に検索できるが,静的なデータ構造のため,更新時のオーバヘッドが大きい.我々は以前,この問題を解決するインクリメンタルな更新方式を提案したが,この方式が残す問題点の1つは,インクリメンタルに追加される情報を用いて作成したsuffix arrayを既存の大きなsuffix arrayに結合する統合処理に依然大きな時間を要することである.本論文では繰返し的な更新処理や検索処理を高速に行うために,インクリメンタルな更新方式を分散並列化した方式を提案する.また,実装を用いた実験結果により,提案方式が更新処理の高速化と検索処理の性能向上に有効であることを示す.Suffix array is a full-text index structure efficient to retrieve any substring of the indexed text, but requires significant overheads to update. Previously we proposed an incremental updating scheme for suffix arrays to solve this problem. One of the remaining problems is the overheads to integrate adding suffix array and existing large suffix array in update operation. Frequency of the integrate operation is reduced in the incremental updating scheme, but it still requires considerable overheads. This paper presents a scheme to incorporate parallel and distributed processing into the incremental updating scheme. In the scheme, decomposed suffix arrays are distributed to several machines, so that the integration overheads are reduced and throughput for the retrieval operations is increased. We show some experimental results conducted to evaluate the proposed scheme.

著者

尾崎 敦夫 松下 和隆 白石 將 渡部 修介 古市 昌一 佐藤 裕幸

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.48, no.13, pp.1-12, 2007-08-15

---

我々は計算機クラスタ環境上において、航空機、艦船、車両等を主対象とする移動体シミュレーションの高速化手法である、動的タイムステップ制御方式(DTSS: event aware Dynamic Time Step Synchronization method)をすでに考案している。しかし、問題が大規模になった場合には、1 つの計算機上でも多数の移動体を高速に模擬することが求められる。本論文では、移動体が道路網上を移動する道路交通シミュレーションを取り上げ、模擬結果を変えずに移動体間の同期および模擬コストを低減させて実行性能向上を図る、道路交通向け動的タイムステップ制御方式(DTSS-RT: DTSS for Road Traffic simulation)を提案する。本方式を災害シミュレータの代表例であるロボカップレスキューの道路交通サブシミュレータへ適用した結果、ひどい渋滞状態がなければ従来方式の約 2~3 倍の性能向上が実現できることが確認できた。We have already proposed DTSS (event aware Dynamic Time Step Synchronization method) for speeding up moving objects (MOs) simulation, e.g. aircraft, ships, vehicles and so on, in a computer cluster environment. However, speeding up the simulation for a number of MOs on a single processor is required as well, when the problem size is enlarged. In this paper, we propose DTSS-RT (DTSS for Road Traffic simulation), which can speed up the simulation by reducing the simulation cost of each MO and synchronization cost between MOs without changing the simulation result. For evaluating DTSS-RT, we employed a road traffic sub-simulator of RoboCupRescue simulation. The results show that the performance of the simulation based on DTSS-RT is improved approximately 2~3 times over that of the conventional method except when the situation includes a heavy traffic jam.

著者

高田 雅美 木村 欣司 岩崎 雅史 中村 佳正

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.47, no.7, pp.91-104, 2006-05-15

被引用文献数

6

---

高精度かつ高速に上2 重対角行列を特異値分解するために,我々は,dLV(離散ロトカ・ボルテラ:discrete Lotka-Volterra)系による新たな特異値分解ライブラリを開発している.既存ライブラリとしては,線形数値計算ライブラリLAPACK におけるDBDSQR がある.DBDSQR は,QRs法に基づいた特異値分解ライブラリであるが,計算量が多く,実行時間の面で大規模向きではない.また,いくつかの特異ベクトルのみを計算することも困難である.一方,dLV 系により定式化されたI-SVD(Integrable-Singular Value Decomposition)法は,計算量が抑えられる動作原理を持つ.本論文では,I-SVD 法の実装ライブラリDBDSLV を開発し,実行時間と計算精度について,DBDSQR との比較数値実験を行う.精度を調べる際,真の特異値と特異ベクトルが判明している上2 重対角行列が必要となる.そこで,Golub-Kahan-Lanczos 法によるテスト行列作成法を用いる.実験の結果,DBDSLV は,DBDSQR よりも誤差の少ない特異値と特異ベクトルを非常に短い実行時間で計算されることが確認された.計算された特異ベクトルの直交性も同程度であり,再直交化を行えばDBDSQR を上回ることも分かった.To perform SVD (Singular Value Decomposition) of bidiagonal matrices with high accuracy and high-speed, we develop a library by using the dLV (discrete Lotka-Volterra) system. Today's standard routine for SVD is DBDSQR provided in LAPACK (Linear Algebra PACKage). Since the computation of SVD by DBDSQR is based on the QRs (QR with shift) algorithm, DBDSQR is slow in speed and is unsuitable for large scaled problems. It is also difficult to obtain only a few singular vectors by using DBDSQR. On the other hand, the I-SVD (Integrable-SVD) scheme based on the dLV system enables us to cut down the computational cost by separating the computation process of singular values and vectors. In this paper, for evaluation of computational time and accuracy, we implement the I-SVD scheme to a new routine named DBDSLV and compare it with DBDSQR. For a comparison of accuracy, we use a method for constructing a class of upper bidiagonal random test matrices having true singular values and vectors by means of the Golub-Kahan-Lanczos method. As experimental results, we confirmed that DBDSLV is faster and errors of singular values and vectors in DBDSLV are smaller than those in DBDSQR. Though the orthogonality of computed singular vectors in DBDSLV is in the same order as in DBDSQR, we found that DBDSLV has a better orthogonality through a reorthogonalization.

著者

鈴木 有也 福田 宗弘 和田 耕一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.44, no.10, pp.141-152, 2003-07-15

---

マルチエージェントに基づく複雑系モデルは,多種多様なエージェントの相互作用によってシミュレートされるため,シミュレーションアルゴリズムの良好な記述性がつねに求められる.そこで本研究では,スレッドで実装されたエージェントがクラスタ上を移動し,相互に作用しながらシミュレーションを進める並列マルチエージェントシミュレータM++を提案する.M++は,M++言語によって記述性を追求し,アルゴリズムに沿ったシミュレーションプログラムのコーディングを容易にする.また独自のS スレッドライブラリ,およびゼロコピー通信を用いたスレッド移動によって性能の低下を軽減し,台数効果を得ることができる.本論文は,人工社会シミュレーションをM++とMPIの双方で記述することによって,M++の記述性を検証し,その性能について考察することを目的とする.The multi-agent approach requires a large number of various agents and objects, where programmability are of essence in such simulations. To improve this feature of the approach, we propose the M++ parallel multi-agent simulator, in which threads represent agents, autonomously navigate through, and get access to a simulation space constructed over a cluster system. We have not only realized a narrow semantics gap between simulation models and their code with our M++ language, but also retained performance using our original sthread library and zero-copy thread migration scheme. In this paper we demonstrate programmability of M++ using artificial societies simulation by comparing with MPI and inspect its performance.

著者

伊賀 徳寿 中本 幸一 奥山 嘉昭 佐藤 直樹 檜原 弘樹

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.44, no.10, pp.164-176, 2003-07-15

被引用文献数

4

---

企業向けシステムでは,システムで提供する機能をオブジェクトとしてモデル化し,相互接続性を保証したCORBAにより実装するシステム構築が広まってきている.オブジェクト指向設計による生産性向上とソフトウェアの下位層の隠蔽による移植性の向上を目的として,組込みシステムから構成されるネットワークシステムでもCORBAは有効であると期待されている.しかし,CORBAは企業システム向けに設計されており,ハードウェアリソースやソフトウェアリソースの制約の厳しい組込みシステムでは適用が難しいところがある.本論文では,企業システムとは直接には接続しない組込みシステムネットワークに特化した機能を有する組込みシステム向けCORBA(Embedded CORBA)の設計思想,仕様,実装とその評価について述べる.最近,情報家電をはじめとする組込 みシステムでは,機器の提供する機能の追加拡張を行う機能が求められている.Embedded CORBAは,このためにオブジェクトの動的追加機能を具備している.In enterprise system, CORBA becomes popular, in which the functionalities the enterprise systems are modeled as objects and the objects are implemented. CORBA is also expected to be effective in embedded system because high productivity of object-oriented design and high portability due to hiding lower software layers. Applying CORBA to the embedded systems is difficult because CORBA is basically designed for the enterprise systems and not suitable for the embedded system whose resources are very restricted in hardware and software. Embedded CORBA is suitable for embedded system networks,which are not directly connected to the enterprise systems. We describe the design philosophies, the specification and design and the implementation and evaluation of Embedded CORBA. Recently, extending functionalities in the embedded systems are required. Embedded CORBA also provides the functionalities to add objects dynamically.