モバイルコンピューティング研究室に変わりました!

ソフトウェア基礎学研究室(教授:伊藤 実)は,2015年4月にモバイルコンピューティング研究室(モバ研)へ変わりました! モバ研では主に,実社会に存在する問題を抽象的に捉えて数学的にモデル化し,計算機で効率よく解くためのアルゴリズムを考案しています.今回はモバ研で行っている研究のいくつかをテーマに分けて紹介します.

高度交通システム

交通渋滞は以前から大きな社会問題であり,二酸化炭素排出などの環境への悪影響や社会活動の滞りなどによって, 社会に悪影響を及ぼしています.当研究室では高度交通システム(Intelligent Transport Systems; ITS)を利用し,交通の効率化や快適化,渋滞の軽減のための研究を行っています.

Keywords: 高度交通システム(ITS), 信号制御, 車々間通信, ナビゲーション, ロードプライシング

GreenSwirl: Combining Traffic Signal Control and Route Guidance for Reducing Traffic Congestion

渋滞を引き起こす原因の一つとして非合理的な交通信号サイクルがあり,信号制御の技術として,GreenWaveが中国の複数の都市で実験されています.しかし,GreenWaveには対向車線と横断道路の妨害,入口と出口の渋滞などを引き起こしてしまう問題があります.そこで研究[1]では,GreenWaveの問題を解決する信号制御方式GreenSwirlと経路案内方式GreenDriveを提案しています.提案手法の性能を評価するために交通流シミュレータSUMOを用いてシミュレーションを行い,ニューヨーク市マンハッタン島の道路網で車両の走行時間短縮効果を計測した結果,従来の手法と比べて提案手法は平均10~70%程度,平均走行時間が短縮できることを確認しました.

[1] Jiaxing Xu, Weihua Sun, Naoki Shibata and Minoru Ito : “GreenSwirl: Combining Traffic Signal Control and Route Guidance for Reducing Traffic Congestion,” in Proc. of IEEE Vehicular Networking Conference 2014 (IEEE VNC 2014), pp. 179-186, 2014-12-15.

モバイル環境を想定したシステムやサービス

Keywords: 無線ネットワーク, 移動体通信, モバイルアドホックネットワーク(MANET), センサネットワーク, 遅延耐性ネットワーク(DTN), データオフロード, 位置推定, 災害復旧, IoT

地下街におけるスマートフォンの光を用いた避難誘導方式

地下街が停電し,避難が必要である状況では,地下街が停電すると,壁や床等が見えない状況下におかれます.そのような状況下では唯一の目印である避難誘導灯を用いて避難することになります.しかし先行研究によると避難誘導灯を利用する避難者は2割程度であり,避難誘導灯は避難誘導の役割を十分に果たしているとは言えません.研究[2]では,避難者の携えるスマートフォンの発する光(バックライトとフラッシュライト,総じてスマホライトと呼ぶ)を用いた避難誘導方式を提案しています.提案手法を用いない3D動画,提案手法を用いた3D動画を著者らの所属する学生3名に視聴させ,5つの評価項目に対して5段階評価で評価するアンケートを実施し,提案手法ありは提案手法なしに比べ,高評価の割合が高いことを確認しました.

[2] 冨永 拓也, 柴田 直樹, 孫 為華, 伊藤 実 : 地下街におけるスマートフォンの光を用いた避難誘導方式の提案, DICOMO2014シンポジウム論文集, pp. 266-277, 2014.7.9.

A Proposal of an Endorsement Based Mobile Payment System for A Disaster Area

A payment system in a disaster area is essential for people to buy necessities such as groceries, clothing, and medical supplies. However, existing payment systems require the needed communication infrastructures (like wired networks and cellular networks) to enable transactions, so that these systems cannot be relied on in disaster areas, where these communication infrastructures may be destroyed. In [3], we propose a mobile payment system, adopting infrastructureless mobile adhoc networks (MANETs), which allow users to shop in disaster areas while providing secure transactions. Specifically, we propose an endorsement-based scheme to guarantee each transaction and a scheme to provide monitoring based on location information, and thus achieve transaction validity and reliability. Our mobile payment system can also prevent collusion between two parties and reset and recover attacks by any user. Security is ensured by using location-based mutual monitoring by nearby users, avoiding thereby double spending in the system.

[3] Babatunde Ojetunde, Naoki Shibata, Juntao Gao, and Minoru Ito : An Endorsement Based Mobile Payment System for A Disaster Area, in Proc. of The 29th IEEE International Conference on Advanced Information Networking and Applications (AINA-2015), pp. 482-489, Mar. 2015.

並列計算・分散コンピューティング

Keywords: 分散処理, GPGPU, クラウド, タスクスケジューリング, P2P, 負荷分散, 映像処理, 可視化, 3Dバーチャル空間, ストリームデータ処理

ライブ放送のための映像処理システムにおける負荷分散方式の設計と実装

著者らは,ライブ放送のための分散型映像処理システムを研究開発しています.本システムでは,映像処理サーバが映像撮影端末から依頼された映像処理を行います.多数の映像撮影端末が映像処理サーバに映像処理を依頼すると通信負荷や処理負荷が大きくなって映像処理に時間がかかり,ライブ放送を円滑に行えません.そこで研究[4]では,映像処理を依頼する映像処理サーバを選択して映像処理サーバにかかる負荷を分散させる方式を提案,実装しています.提案方式では,複数の映像処理サーバがある場合に,映像処理内容や負荷に応じて処理を依頼する映像処理サーバを,P2P型モバイルエージェントシステムを用いて選択します.複数の映像処理サーバと映像撮影端末を用いて実験し,映像処理を完了するまでの時間への影響を確認しました.

[4] 川上 朋也, 石 芳正, 義久 智樹, 寺西 裕一 : ライブ放送のための映像処理システムにおける負荷分散方式の設計と実装, 第8回データ工学と情報マネジメントに関するフォーラム (DEIM2016) 論文集, 2016年3月.

最後に……

モバ研の詳細やそのほかの研究内容については,研究室のWebサイトをご覧ください.見学や質問も随時受け付けていますので,お気軽にお問い合わせください!

Posted in 未分類 | モバイルコンピューティング研究室に変わりました! はコメントを受け付けていません。

計算機で言語の謎を明らかにする

こんにちは、自然言語処理研究室助教の能地です。

自然言語処理というのは、コンピュータの上で言語を扱う研究全般を指します。分かりやすい研究分野だと、ある言語の文章を別の言語の文章に変換する機械翻訳などが該当します。私はこの分野の研究を始めて5年ぐらいですが、今日は私がこれまで取り組んできた、自然言語処理の中でも少し変わった切り口の研究を紹介してその面白さを伝えられたらなと思っています。 Continue reading

Posted in 未分類 | 計算機で言語の謎を明らかにする はコメントを受け付けていません。

Dakar – Nara Rally

On a Monday a triple of decades ago, I came into this world weighting a little more than what a normal baby would weight. Paradoxically, I grew up in Dakar the capital of Senegal as a very thin boy, so thin that people would call me in Wolof “kilo bopp libaramou yaram” which literary means of 1kg of head and ½ kg of body. To that thinness, I added a layer of timidity which I do not know if it was the result of some genes I inherited from my parents or just a byproduct that comes with being thin.

Fast forward… After I graduated from high school, I enrolled in the Physics and Chemistry department of the Faculty of Science and Techniques of the University Cheikh Anta Diop of Dakar. I remember my old brother being extremely puzzled by my choice as I was always burning his eardrums about my natural business acumen and how I would grow up and become a great businessman. It was clear in his mind that I was going to study business and management. But in my head I was like I have a plan that, besides me, nobody else can understand. The reality is that I might just have succumbed to pride as I was like I wouldn’t work so hard in high school to attend university with people who have not spent as much blood, sweat and tears in science as I did.

I went to the Physics and Chemistry department where I obtained a bachelor degree in Physics. There is a saying at the university Cheikh Anta Diop as: “the rule is to fail the exam; the exception is to pass at your first try.” In a department as the Physics and Chemistry, that saying was closer to reality than in any other departments. But I had no intentions to waste my time in the university and as a result, those years have arguably been my most difficult years in terms of wanting to succeed and the amount of work I put into my studies. I did not regret it because I graduated with high marks which have opened new opportunities for me.

After my bachelor in physics, I had heard of a new master program that fascinated me. The master was about cryptography and information security and was unique at that time in Senegal in particular and in west Africa in general. Fortunately, they were offering a scholarship to which I postulated and successfully secured it. It was fun for me to study new things and after a year in the program, I was enjoying all the new things I was studying but I was also missing the challenges that I was having studying physics. Those days where I would spend hours trying to understanding an equation and the gratification that comes after figuring it out. During the second year of the master program, one of my classmates told me about the MEXT scholarship and recommended me to apply. I was not very excited to do so as the processes of selection of most scholarships in my country are not very transparent, not to say that they are very opaque. But this one was different as the personnel of the embassy of japan in Senegal was taking care of the selection. Still, I wasn’t very convinced but as I had an appointment near the office where they were receiving the applications therefore I decided to give it a try.

I asked my friend to meet there and to my surprise, after so much effort in convincing me, he couldn’t come due to some other matters he had to take care of. So I went to the office with an incomplete application folder and applied. A couple of days later, I received a phone call from the then head of the culture department at the Japanese embassy in Dakar. He urged me to complete my application by sending the files that were missing. I saw the phone call as a huge boost of my confidence and decided to be more diligent into that application process. So I completed my application and did all the tests that were required. After that, I just had to wait to hear back from them whether I was retained or rejected.

Growing up, I never really fantasized about going to Japan. Things I knew about the country were stereotypical things I learned from movies and urban legends. But Japan has always been mysterious, I always wondered how a country that has gone through so much pain is part of the top 3 most developed countries in the world. I saw Senegal as a younger brother of Japan as we are similarly devoid of any natural resources and count on the ingenuity of the denizens to develop the country. Tough I never dreamed of going to japan, I knew very well the level of advancement of the country of the rising sun and understood that this was a good opportunity for me to learn from the best in order to later help my country level up with the best countries in the world.

Nearly 4 to 5 months after I concluded the scholarship application process, I received an email from a member of the International Division, informing that professor Suguru Yamaguchi has accepted me in his laboratory, Internet Engineering, located in Nara Institute of Science and Technology (NAIST). I could not express how happy and excited I was to join Japan. But I was equally puzzled by learning the school that was going to host me: NAIST. When I googled universities in japan, I always found the universities of Tokyo, Osaka, Kyoto or again Waseda and Keio but never NAIST. But a quick google search, with the right keywords, showed that NAIST was actually one of the top ranked national universities. That was enough to dissipate my doubts.

I arrived in Japan on April 5th, 2010. At first, I was residing in Osaka because I had to take a six months’ Japanese language training course. Afterwards, I joined NAIST and started as a research student. During that period, I learnt how to conduct high level research by reading and summarizing world class papers. It was not easy because it was novel to me but I could succeed through perseverance. I passed the master exam and started my journey as master student. In terms of research I wanted to work on something that was the most interesting topic in my field. At that time, cloud computing was the darling in computer science. More precisely, the adoption of cloud computing heavily depended on its security issues so I decided to focus on researching security mechanisms for cloud computing. For the master thesis, I developed a security quantification mechanism that allows administrators to quantification the security of their Infrastructure as a Service (IaaS) cloud environment.

IMG_1026

Fig 1: Master’s degree graduation ceremony

I graduated from the master course in September 2012 and started the PhD course in October of the same year. I pursued the same research topic by fine tuning my master thesis topic and proposing an authorization mechanism for cloud computing that challenge the common knowledge in terms of practices in information technology. I successfully defended my Ph.D. and graduated in September 2015.

IMG_7992

Fig 2: Ph.D. degree graduation ceremony

Since October 2015, I am an Assistant Professor in the Internet Engineering Laboratory (IPLab), Graduate School of Information Science, Nara Institute of Science and Technology.
I will conclude this entry with the abstracts of two of my publications.

Security Risk Quantification Mechanism for Infrastructure as a Service Cloud Computing Platforms
Cloud computing has revolutionized information technology, in that It allows enterprises and users to lower computing expenses by outsourcing their needs to a cloud service provider. However, despite all the benefits it brings, cloud computing raises several security concerns that have not yet been fully addressed to a satisfactory note. Indeed, by outsourcing its operations, a client surrenders control to the service provider and needs assurance that data is dealt with in an appropriate manner. Furthermore, the most inherent security issue of cloud computing is multi-tenancy. Cloud computing is a shared platform where users’ data are hosted in the same physical infrastructure. A malicious user can exploit this fact to steal the data of the users whom he or she is sharing the platform with. To address the aforementioned security issues, we propose a security risk quantification method that will allow users and cloud computing administrators to measure the security level of a given cloud ecosystem. Our risk quantification method is an adaptation of the fault tree analysis, which is a modeling tool that has proven to be highly effective in mission-critical systems. We replaced the faults by the probable vulnerabilities in a cloud system, and with the help of the common vulnerability scoring system, we were able to generate the risk formula. In addition to addressing the previously mentioned issues, we were also able to quantify the security risks of a popular cloud management stack, and propose an architecture where users can evaluate and rank different cloud service providers.

Risk Adaptive Authorization Mechanism (RAdAM) for Cloud Computing
Cloud computing provides many advantages for both the cloud service provider and the clients. It is also infamous for being highly dynamic and for having numerous security issues. The dynamicity of cloud computing implies that dynamic security mechanisms are being employed to enforce its security, especially in regards to access decisions. However, this is surprisingly not the case. Static traditional authorization mechanisms are being used in cloud environments, leading to legitimate doubts on their ability to fulfill the security needs of the cloud. I proposed a Risk-Adaptive Authorization Mechanism (RAdAM) for a simple cloud deployment, collaboration in cloud computing and federation in cloud computing. I used a fuzzy inference system to demonstrate the practicability of RAdAM. I complemented RAdAM with a Vulnerability Based Authorization Mechanism (VBAM) which is a real-time authorization model based on the average vulnerability scores of the objects present in the cloud.

Posted in 未分類 | Dakar – Nara Rally はコメントを受け付けていません。

スマートホームでの一日



AM6:47,カーテンが自動で開く音と,いつものあの曲で目が覚める.30分程前にスイッチがついたエアコンのおかげで部屋は暖かく,なんの躊躇もなく布団から抜け出す.起床予定はAM7:00だけれど,眠りの浅いタイミングを見計らって起こしてくれるので,毎日すんなり起きられて,二度寝して遅刻することもない.
シャワーを浴びて部屋に戻ると,少し暖房が抑えられたリビングでテレビがスイッチオン.自分の関心事を学習済みのテレビから,昨夜の野球の結果と今日の天気、そしてお気に入りのアイドルのニュースがダイジェストで流れてくる.どうやら通勤経路で事故が発生しているらしいし,夕方からは雨になるらしいので,折りたたみ傘を持って10分早く外出する.以前は,電気やエアコンを消し忘れることもあったが,今はスマートホームが消してくれるので心配ない.余計なことを考えず,今日も一日集中!

夕方
仕事を終えた後,スーパーによってから帰宅.不在時に家を綺麗にしてくれていたお掃除ロボットが,帰宅時間を察知して玄関でお出迎え.部屋に入れば,加湿器とエアコンが部屋を快適にして待っていてくれる.購入した品物を冷蔵庫にしまうと自動で在庫リスト作成し,スマートフォンで閲覧可能にしてくれる.おかげで,今日は朝食用の納豆を買い忘れずに済んだ.
音楽を聴きながら一休みした後,夕食を作り始めるとエアコン・加湿器が停止し,部屋が無駄に暑くなることを防いでくれる.よく歩いたこんな日には,スタミナ料理のレシピが推薦されていて,冷蔵庫にも「ビールOK」のサイン!健康も考えられた至極の一杯.
夕食後はいつもの読書の時間.音量が自動で絞られ,スタンド以外の電気が少しおとされる.この時間が,私のリラックスタイム.落ち着いた気持ちで布団に入る.もちろん,スマートフォンを枕元におくことを忘れない.こいつのおかげで,入眠を察知したエアコンが自動で温度調整してくれるし,朝もしっかり起こしてくれる.快適な睡眠・生活に欠かせない相棒である.さて,明日も一日がんばろう.


smarthome

スマートホーム

さて,こんな生活を送るためには,どんな技術が必要でしょうか?まず,重要になるのがコンテキスト(居住者の状態)の認識です.言い換えると,「シャワーを浴びる」「外出する」「夕食を作る」「読書する」など,居住者の生活行動を認識する必要があります.我々は,どうすれば人の生活行動を認識できるかを明らかにするために,多数のセンサを設置した1LDKのスマートホームを大学内に設置し,実験を行っています.スマートホームには,一般家庭にあるような家電やお風呂なども備わっていて,実際に住むことができます.2泊3日程度の実験宿泊から,これまで最長で2週間ほど滞在した人もいます.
スマートホームで行動認識を行う際にポイントになるのが,可能な限りプライバシーに配慮したデータ収集と,コストの低減です.例えば,たくさんのビデオを設置し画像解析することでも人の生活行動は認識できます.しかしながら,毎日ビデオカメラで監視されている生活を想像してみてください.嫌ですよね.そこで我々は,プライバシーに配慮するために,スマートハウス内における人の位置情報と家電の電力使用量のみを利用して生活行動を認識しようと試みています.
次に,コストの低減ですが,我々のスマートハウスには人の位置情報を誤差10cmで測定できる超音波センサが設置されています.とても高精度なセンサですが,非常に高価で一般家庭に普及できるものではありません.そこで我々は,あえて位置情報の測位精度を劣化させた場合を想定した実験を行っています.同様に,電力使用量を計測するセンサも16個設置されていますが,あえて測定する電力計の数を減らした実験を行っています.

overview

提案手法

その結果,高精度・多数のセンサを使用した場合,「テレビ視聴」「読書」「食事」「睡眠」「仕事・勉強」「入浴」「掃除」「料理」「食器洗い」「外出」の10の生活行動を95%以上の精度で判定可能であることを確認しています.さらに,位置と電力使用量の精度を部屋単位に落とした場合でもあっても,85%以上の精度で判定可能であることを明らかにしています.つまり,プライバシーに配慮しながら低コストで生活行動を判定することが可能であるということです.こうした生活行動の認識と,部屋に設置された環境センサやスマートフォンのセンサを組み合わせることで,入浴や料理に応じて暖房や加湿を抑えたり,読書や外出を判定して照明を調整したりすることができるようになります.

では,「眠りの浅いタイミングを見計らって起こしてくれる」や「入眠を察知したエアコンが自動で温度調整」を実現するためには,どうすればいいでしょうか?これを実現するためには,人の眠りの深さをセンシングする必要があります.一般的に,睡眠段階は5段階に分類されます.この計測は,専門の機器を使えばそう難しいことではありませんが,一般家庭にそんな機器はありません.では,どうしたらよいのでしょうか?

スマートフォンによる脈拍測定

スマートフォンによる脈拍測定

我々はスマートフォンに着目しました.スマートフォンは,我々にとって非常に身近で優秀なセンサデバイスなのです.例えば,スマートフォンの加速度センサを使えば体動を検知することができます.また,カメラとフラッシュライトを使うと脈拍が取れます.この脈拍の変化を利用することで睡眠状態を推定しようと試みています.

まず,スマートフォンアプリケーションによる脈拍数推定手法を開発しました.評価実験の結果,2分間の測定おいて,心拍計と比較して十分な測定精度であること(平均誤差1.83bpm)を確認しています.次に,ここで得られた脈拍データと睡眠状態データを機械学習することにより睡眠段階の識別モデルを構築しました.その結果,脈拍のみを用いて人が眠っているか起きているかを90%の精度で推定できることを明らかにしています.このようにスマートフォンを利用して人の睡眠状態を認識することで,その人の状態に合わせた家電制御ができるようになります.これできっと将来は夏の寝苦しい夜にエアコンのリモコンと格闘することはなくなります.
スマートフォンを用いたコンテキスト認識の研究対象としては,睡眠状態の判定だけでなく,人の空腹度推定や健康状態の推定,心理状態の推定なども行っています.いつでも持ち歩くスマートフォンと連動することで,スマートホームは食事の時間や献立を勧めたり,情緒不安定のときには部屋をリラックスできる調光や音楽で満たしたりすることが可能となります.我々,ユビキタスコンピューティングシステム研究室では,そんなスマートホームの実現に向けたさまざまな研究を行っています.

ユビキタスコンピューティングシステム研究室では,未来のユビキタス社会の実現を目指し,センサ・デバイス・ネットワークが連携し,センサから取り込まれる実世界データを処理・集約・解析することで,高度なサービスを効率よくユーザに提供するシステム=ユビキタスコンピューティングシステムの実現に向けた研究に取り組んでいます.スマートホームだけでなく,実世界の問題に対して「情報の収集」,「収集した情報の分析」,「分析結果の応用」の三位一体で取り組み,具体的には以下の研究を行っています.

kenkyu
研究内容や研究室に興味がありましたら,ユビキタスコンピューティングシステム研究室のホームページもご覧いただけると幸いです.見学や質問は随時受け付けています.

文責:助教 諏訪 (h-suwa@is.naist.jp)

Posted in 未分類 | スマートホームでの一日 はコメントを受け付けていません。

ディペンダブルシステム学研究室2014

ディペンダブルシステム学研究室では、ディペンダブルなシステム、すなわち、ユーザが信頼して使うことのできるシステムを提供するための様々な研究を行っています。その中でも力をいれているのは、分散アルゴリズム、LSI高信頼化設計、LSIテストです。ディペンダブルシステム学研究室では、今年度、それぞれの分野で新たな取り組みをしました。

もののインターネットであるIoT時代が到来し、インターネットをはじめとする分散システム、ICTの基盤であるLSIのディペンダビリティは益々重要となっています。ディペンダブルシステム学研究室では、高度な故障耐性を持つ分散アルゴリズム(分散システムのためのアルゴリズム)である自己安定アルゴリズムの研究に取り組みました。また、LSIのディペンダビリティ向上のためにも2つのテーマに新たに取り組みました。LSI高信頼化設計では、これまで取り組んでいたロジックの高信頼化設計に続き、メモリの高信頼化設計にも取り組みました。さらに、プロセステクノロジーの微細化により、益々複雑化するLSIテストの品質向上のために、テスト時の電源ノイズを考慮した高品質なテスト技術の開発にも取り組んでいます。

今年度、新たに取り組んだ3つのテーマを紹介します。

自己安定アルゴリズム

分散システム、コンピュータネットワークの大規模化は益々すすみ、システムの内に故障が発生するということを前提としたディペンダビリティの考え方が重要になっています。システム内に故障が発生した場合、システムの稼働を一旦中断してメンテナンスする手段と、稼働させたままシステムを安定化させる手段が考えられます。

自己安定アルゴリズムは、コンピュータネットワークで代表される分散システムのための故障耐性を持つアルゴリズムで、システムがどんな状態になってもシステムを稼働させたまま正当な状態までシステムを遷移させ安定させることが可能です。そのため、故障によりシステム内のいくつかのコンピュータが管理する変数の値が改ざんされ、システムがつじつまの合わない状態に陥っても、自己安定アルゴリズムはシステムを自力で正当な状態に戻すことが可能です。また、システムを構成するコンピュータや通信リンクの追加や離脱などによるトポロジー変化にも柔軟に対応する、システムの初期化が不要など様々なメリットを持つアルゴリズムです。

ディペンダブルシステム研究室では、今年度、この自己安定アルゴリズムの研究に新たに取り組みました。特に、コンピュータネットワークをグラフと捉え、グラフ理論の諸問題を解く自己安定アルゴリズムに取り組んでいます。グラフ理論とは、複数の「ノード」と「ノード」と「ノード」との関係をグラフというデータ構造で表して考える様々な応用を持つ理論です。例えば、鉄道の路線図、電気回路・電子回路の回路図、SNSでの友達関係などもグラフで表現できます。

自己安定アルゴリズムに関する今年度一番の成果は、「匿名ネットワークで1−極大マッチングアルゴリズムを解くサイレントな自己安定アルゴリズム」です。

タイトルを説明するにはたくさんの概念を説明する必要があるので、思い切って省略しますが、マッチングとはノードのペアを作ることで、ペア数をなるべく多く作ることを目標とするアルゴリズムです。例えば、男女のカップルをたくさん作るという問題などを連想するとよいかもしれません。

この問題に関して、「匿名」、「1−極大」、「サイレント」、書いていませんが「集中型デーモン」、「木・リング」などの問題設定の下で、既存のアルゴリズムはO(n4)ムーブという性能だったのを、私たちが提案したアルゴリズムではO(n)ムーブに改善しました。ムーブというのは、1ノードが周りのノードの状態を見て、自分の状態を遷移させる動作です。提案するアルゴリズムは、このムーブをノード数nに比例する回数行えば、どんなシステム状態からでも1−極大マッチングというマッチング数が多い状態に遷移することを保証します。アルゴリズムの実行例を図1に示します。各ノードは、自身とリンクでつながっている隣接ノードの状態だけから、どのノードを誘うか、どのノードとペアになるかを決定し、これを繰り返すと、システム全体がいずれ「1−極大マッチング」状態に到達します。自己安定アルゴリズムの面白いところは、各ノードがローカル情報だけで状態遷移を行うにもかかわらず、システム全体がグローバルに安定するところです。

自己安定アルゴリズムの研究は、各ノードの振る舞いを記述するアルゴリズムを考案し、それがどんな場合でも期待通りに動くことを証明し、その性能を数学的に解析する計算理論と呼ばれる分野の研究です。数学的なモデル上でエレガントなアルゴリズムを理論的に解析して楽しんでいます。

研究成果は、International Workshop on Algorithms and Computation (WALCOM2015) で発表しました。

SSmatching

組み込みメモリの高信頼化

メモリとロジックを混載するシステムオンチップ(SoC)内の組み込みメモリのサイズや集積度が大きくなっており、メモリの故障、エラーがSoCの歩留まり、信頼性に大きく影響します。ここで、故障とはメモリ内部に起きたハードウェア的な欠陥を意味し、エラーとはメモリが誤った値を出力することを意味します。エラーには、故障が原因となるハードエラーと、アルファ線などがメモリセルに衝突しセルの値が反転するといったメモリ外部の要因によるソフトエラーとがあります。ソフトエラーを訂正するために、ECC(誤り訂正符号、Error Correcting Code)やScrubbingという手法が用いられています。Scrubbingとは、メモリに格納された値を読み出し、ECCを用いてエラーを訂正した値を再度書き込みメモリからエラーを消去する手法です。

ECC

ここで、ECCと1ワード中のエラー数との関係を考えてみましょう。図2では、ECCは1ワード中の1エラーのみ訂正可能とします。このとき、1ワード中にエラーが1個であれば、ソフトエラーでもハードエラーでも訂正可能です。ソフトエラーの場合は、新しい値を上書きする(overwrite)、またはscrubbingによりメモリの値は正しい値になります。一方、ハードエラーの場合、上書きやscrubbingでもエラーが残ることがあるため、同じワードに新たにエラーが起これば、誤り訂正ができなくなってしまいます。

そのため、故障対策としては別の手段として、冗長回路を用いたメモリの修復が考えられています。オンラインメモリ修復として、リマップCAM (Content Addressable Memory, 連想メモリ)を用いた手法が提案されています。この手法は、故障セルを含むワードを正常なスペアワードに置き換えるためにアドレスをメモリ内部で置き換える手法です。

ディペンダブルシステム学研究室では、今年度、ECC, Scrubbingによる誤り訂正とリマップCAMを用いたオンライン修復を組み合わせ、メモリの寿命を延ばす手法の提案に取り組みました。提案手法では、稼働中のシステムに組み込まれたメモリに対し、セルフテスト(BIST, Built-In Self-Test)を定期的に行い、リマップCAMの再構成を行います(図3)。このとき、ワード中のエラー数に応じて優先度を設けて、修復対象となるワードを決定します。図3中のDiagnosis CAM は、BISTの結果を集約し同一ワード内のエラー数を特定するために用いられます。

図4は、提案法と既存法とでメモリの信頼性を評価した結果です。ここで、既存法とは誤り訂正不可能となったワードのみを修復する手法です。信頼性とは時間の関数で、その時間までシステムが正常に稼働する確率を表す指標であう。信頼性の評価は、ソフトエラー、ハードエラーがポワソン分布に従って発生すると仮定して行いました。評価の結果、提案法では信頼性の高い期間が長く、従来法と比較してメモリの寿命が延びていることが確認できました。

研究成果は、IEEE Workshop on RTL and High Level Testing (WRTLT2014)で発表し、IEEE European Test Symposium(ETS2015)でも発表します。

OLRepair

 

Reliability2

LSIテスト時の電源ノイズの低減

LSIテスト時の過度の電源ノイズによる誤判定が問題になっています。LSIの良・不良を選別するテストによって正しい判定ができないと、不良品の市場流出や、良品の破棄に繋がってしまうため、テストには高い品質が求められています。本研究ではテスト時の電源ノイズを低減するため、テスト時の最適クロック周波数選択手法を提案しました。

LSIのテストでは、テスタ上のLSIにテストパタンと呼ばれる入力信号を印加し、その応答がシミュレーションで求めた正常応答と一致するかどうかで良否の判定をします。全てのテストパタンで応答が一致したものだけが良品として出荷され、不一致が起こったものは破棄されるか、原因の解析がなされます。ここで、テストの結果が必ず正しいとは限らないことに注意しなければなりません。印加するテストパタンや、テスト時の温度・電圧によっては、誤った判定を下してしまうおそれがあります。欠陥のあるLSIを良品と判定してしまうと(アンダーテスト)、不良品をユーザに販売することになり、使用中の誤動作による事故や、メーカとしての信頼の損失に繋がります。反対に、機能的に問題のない回路を不良品と判定してしまうと(オーバーテスト)、歩留り(良品率)を低下させてしまい、コスト高に繋がります。このように、テストの誤判定は様々な問題を引き起こすため、正しく良否を判定することが求められます。

その一方で近年、LSIテスト時の過度の電源ノイズによる誤判定の問題が深刻になっています。テストでは短時間に回路の隅々まで検査をしたいという要求から、通常起こり得ないような状態遷移を発生させます。これにより回路の動作率が高くなり、消費電流は通常動作時の数倍にもなります。消費電流が大きくなると回路の電源電圧が過剰に低下し、トランジスタが動作しなかったり、信号の伝搬遅延が増加したりします。その結果、回路は誤動作を引き起こし、オーバーテストをもたらします。

電源ノイズは大きく、IRノイズ、Ldi/dtノイズ、共振ノイズに分類されます。IRノイズは、回路中の抵抗成分(R)とそこに流れる電流(I)によって起こる電圧降下を指します。また、Ldi/dtノイズは回路中のインダクタンス成分(L)と電流の変化(di/dt) によって起こる電圧降下を指します。そして本研究で対象とする共振ノイズは、回路中のインダクタンス成分(L) とキャパシタンス成分(C) が構成するLC 回路の共振現象によって起こる、電源電圧の変動を指します。この変動は共振周波数1/(2π√LC)の電流によって励起され、回路の抵抗が小さい場合、減衰しながら数クロックサイクルにわたって振動を続けます。

wave

さらに、共振ノイズは電流が変化するたびに発生し、最終的な電圧変動量は発生した共振ノイズ波形の重ね合わせとなる特徴があります。したがって、印加するテストパタンとその時のクロック周波数により、共振ノイズの影響は変動します。我々はこの点に着目し、与えられたテストパタンに応じて最適なクロック周波数を決めてやれば、共振の影響を低減できると考えました。提案手法はSPICEなどの回路シミュレータを用いることなく電圧変動を計算でき、共振ノイズの少ないクロック周波数を高速に求めることができます。ベンチマーク回路を用いた実験では、提案手法によって選択された周波数によって、最悪時のノイズを50%以上低減しました。また、計算時間は商用回路シミュレータの約1800倍を実現しました。今後は電源回路モデルの詳細化によって、提案手法の精度を向上していく予定です。

ディペンダブルシステム学研究室が今年度新たに取り組んだ、自己安定アルゴリズム、組み込みメモリの高信頼化、LSIテスト時の電源ノイズの低減を紹介しました。研究室の詳しい情報は、研究室HPもご覧ください。

Posted in 未分類 | ディペンダブルシステム学研究室2014 はコメントを受け付けていません。