特定領域研究
「新世代の計算限界」 ニュースレター 第 4 号 2006/1/27
はじめに
このニュースレターは，特定領域・新世代の計算限界のメンバーの情報交換と交流を目的とした情報発信誌です．毎回，いくつかの研究関連の記事と，特定領域のスケジュール・活動報告と，各研究者の活動予定などをお送りいたします．今回は，名古屋大学高木直史先生の研究科紹介と，11月に行われた全体会議，幹事会の報告を行います．
１．中心？隙間？それとも辺境？ − 高木 直史 (名古屋大学)
２．第３回全体会議の報告 − 平田富夫（名古屋大学）
３．2005年度第2回幹事会議事録 − 事務局
中心？隙間？それとも辺境？ 高木 直史 (名古屋大学)
■ 集積システム論
主要大学の中では少し遅れをとりましたが、名古屋大学でも2003年４月に情報系の大学院研究科として、情報科学研究科が設立されました。計算機数理科学専攻、情報システム学専攻、メディア科学専攻、複雑系科学専攻、社会システム情報学専攻の５つの専攻からなっています。本特定領域研究には、計算機数理科学専攻の平田先生、柳浦先生（昨年１０月に転入）も参加されています。（藤戸先生は豊橋技術科学大学に転出されました。）私と高木一義先生は情報システム学専攻の集積システム論講座（大講座：３研究室）に所属しています。
集積システム論というと、半導体回路工学等をイメージされるかもしれませんが、集積回路で構成されるシステムが対象であり、いわゆるシステムＬＳＩや組込みシステムのハードウェア（アーキテクチャ）やソフトウェアに関する研究を行う学問と考えています。現在、年間100億個以上のマイクロプロセッサ（４ビット以上）が出荷されていますが、そのうち、パソコンやワークステーション等の汎用のコンピュータに用いられるのは２％程度であり、ほとんどが組込み用に使われています。実際、あらゆる家電製品にマイクロプロセッサが組み込まれており、一般家庭で40〜50個はあるといわれています。また、自動車にも多く使われており、高級車では70〜80個使われています。
以前は、集積回路を部品として汎用コンピュータを作るために、汎用機のアーキテクチャ、汎用機のＯＳ、汎用機のソフトウェア、そして部品としてのＩＣ設計の研究が行われていました。しかし、今は、コンピュータ（プロセッサ）は部品となり、メモリや種々の周辺回路とともにボード上、さらには、一つのＬＳＩ上に集積されています。集積（組込み）システムのアーキテクチャ、組込み用プロセッサのアーキテクチャ、組込みＯＳ、組込みソフトウェア、そしてシステムとしてのＬＳＩ設計の研究が必要です。
私は、集積システム論は、電気・情報分野の「中心」に位置すると思い（たく）、実際、産業界はシステムＬＳＩや組込みソフトウェアの高度技術者を必要としているのですが、残念ながら、我国の大学では電気電子の分野と情報の分野の「隙間」になっています。企業では、半導体技術者等を社内再教育でこの分野に振り向けているのが現状です。
■ 集積システムの設計支援とハードウェアアルゴリズム
これまでは、本特定領域研究の皆様にはピンと来ない話だったかと思います。しかし、実は、集積システムの設計過程は、組合せ最適化問題の宝庫です。処理のどの部分をハードウェアで行いどの部分をソフトウェアで行うか等を決めるシステムレベルの設計から、LSIのレイアウトまで、最適化問題を解く作業の連続です。最適化の対象は、計算時間や面積に加え、消費電力が重要になっています。ちょっと意外かもしれませんが、よく現れる処理は、ソフトウェアで行うよりハードウェアで行った方が消費電力が少なくて済みます。製造手順の最適化もあります。少し前の話になりますが、ＩＢＭの岩野さんらが、プリントボードに多数のホールを開ける作業を、巡回セールスマン問題の解法を応用して効率化されたことを覚えておられる方もおられると思います。
本特定領域研究には、「ハードウェアアルゴリズムの評価に関する研究」という課題で参加させて頂いています。ハードウェアアルゴリズムの評価は、それの基づく回路の性能によって行います。そのためには、回路の安定したモデルが必要です。従来、組合せ回路モデル上での段数および素子数、さらには、配線領域も考慮したVLSIモデル上での面積が評価基準として用いられています。段数は計算時間の指標ですが、現実には、論理ゲートでの遅延よりも配線での遅延の方が大きくなっており、配線遅延を含めた計算時間を評価できる回路モデルと評価基準の確立が必要だと考えています。また、消費電力を評価するための回路モデルと評価基準も必要だと考えています。
近年、LSIの配線層数が増えてきており、さらに、先日、東北大学でLSIチップを貼り合わせた３次元ＬＳＩが開発されました。３次元のVLSIモデルも興味深い研究課題ではないかと思います。
我々の研究は、本特定領域研究では「辺境」に位置しますが、皆さんにとっても、いろいろ面白い課題があると思います。
第３回全体会議の報告 平田富夫（名古屋大学）
昨年の１１月２１日、２２日に開かれました第３回全体会議についてご報告いたします。
これまで科研の集会というと研究発表のみというスタイルが多かったと思いますが、前回６月の第２回全体会議では、メンバーのコラボレーションを促進することを主目的として各研究班を紹介するポスターセッションがもたれました。（そのコンセプトは前回の全体会議企画担当の浅野哲夫先生の記事（ニュースレター第３号）をご覧ください。）
第３回の全体会議もこのコラボレーション路線を引き継ぎました。今回はオープン問題を持ち寄り共同でチャレンジすることをメインにしましたが、この企画は、第２回全体会議の直後に浅野哲夫先生と岩間先生にご相談して決めたものです。皆さんがお持ちのオープン問題で全体会議に話題提供できるものを募集したところ５人の先生方が応じてくださいました。この場を借りてこの５人の先生方にお礼申し上げます。私の印象としては、だれもがすぐ理解でき、しかもアイデアが出せそうな問題で非常によい問題だったと思います。中には他のメンバーの結果と結びついて発展した話題もあったようです。このような試みは短期的な成果を求めるのが目的ではありませんが、これを機会にひとつでも成果に結びつくものが出てくれば今回の全体会議は大成功といえます。
２日目の講演はSODA、FOCSで発表を予定しているメンバーを中心に、私と柳浦先生が興味をもっている話（は皆さんも興味があるだろうと勝手に考えて）で人選させてもらいました。内容はレベルが高く楽しめたのではないかと思います。ご講演いただいた５人の先生方にこの場を借りてお礼申し上げます。
場所は初日が野依記念学術交流館で、２日目がIB電子情報館大講義室でした。野依記念学術交流館は野依良治先生のノーベル賞受賞を記念して建てられた瀟洒な建物です。カンファレンスホール（２００席）と会議室８室（１室１０名〜２０名、間仕切り撤去可）があり、オープン問題セッションの後のディスカッションにはうってつけでした。この会場は人気があり早くからの予約が必要ですが、今回はたまたま１日だけあいていたので使わせてもらいました。
６月に次回会議の日程を決めたにもかかわらず、私の不手際で会議の直前まで案内をだすことができませんでした。伊藤先生はじめ事務局の先生方にはご心配をおかけしました。幸い柳浦先生が１０月に名古屋大学に着任されてからは進捗著しく無事会議を終えることができました。ご協力いただいた皆様に感謝します。
2005年度第２回幹事会議事録 事務局
日時：2005.11.21, 16:00--17:30
場所：名古屋大学 野依学術交流館 カンファレンスホール
[活動報告]
○ミニ研究集会
・組合せゲーム・パスル（9/12, 京大）
・複雑ネットワーク・ウェブグラフ（9/13, 関学）
・列挙アルゴリズム（9/27--29, 群馬大）
・Complexity（10/11, 東工大）
○ポスドク
・西村治道（10月〜, 京大）
○招聘研究者
○国際会議渡航補助
・FOCS（河原林[東北大]）
○事務員
・宮本希（８月〜）
○国際会議 ランダムネス [渡辺]
7/18--21, 東北大学
[進捗状況報告／討論]
○教科書シリーズ [杉原]
順調。脱稿２件
○ニュースレター [牧野・宇野]
・これまでに３回発行。４回目は来年の１月。
・年に２回程度の予定で進めたい。->了承 (必要ならば、号外を適宜。)
○電子ジャーナル [定兼]
・引き続き、検討を続ける
・協力が必要な場合は、後日に相談
○春学校、ワークショップ (2/27(月) 〜 3/3(金))
・オーガナイザ・プログラム：浅野孝夫
・ローカルアレンジ：西野・垂井
・2/27(月) 〜 3/1(水) 春学校
- 電通大図書館 AV教室 (301号室, 306号室)
- 講師は５名
・3/2(木) 〜 3/3(金) ワークショップ
- 調布クレストンホテル
・春学校 … 初学者の道案内を目指す (定員 90名)
(※ 参考: 春学校に参加させてみたい学生数 … 会場だけで 30名以上)
近隣の諸国にもアナウンスを流す
・春学校/ワークショップではregistration fee を徴収する (高額ではない)
○ミニプロジェクト
・ゲーム [伊藤]
- ミニ研究集会を開催
- 今後、スクールみたいなのを開催したい
・Complexity [垂井]
- ミニ研究集会を開催、今後も開催予定
- 学生にも声をかけたい
・ジオメトリ [加藤]
- ３月後半、学生対象の mini school
- 講師 加藤・浅野・徳山・(David Avis)
・列挙 [中野]
- ミニ研究集会を開催
○電子情報通信学会 特集号 [増山]
・来年６月に、和文論文誌、特定の解説論文の特集
○ICALP ワークショップ
・SATの厳密解法関係のミニワークショップの提案（渡辺先生）
- ヨーロッパの人々とも相談する必要あり
（後日、渡辺先生によって申請、採録された。）
○電子情報通信学会 英文論文誌 [和田]
・来年の８〜１０月頃、〆切は２月頃
・基本は研究論文 (解説論文も ok かも)
・もう少し検討
○予算の使途
・国際会議発表のための海外渡航の補助
○次回の全体会議
・九州地区（山下、定兼）
・2006年、５月か６月頃
○電子情報通信学会 全国大会 企画 [山下]
・3月24日(金) 〜 27日(月) 国士舘大学
・若手(主に博士課程の学生)のためのシンポジウム
・参加費と旅費は、総括班から支援
○次回以降の春学校/ワークショップ
・来年度からは、時期を夏休みぐらいにしたい
・早急に内容の相談を始める必要がある
○EATCS記事募集 [牧野]
・特定内外で、記事があれば、牧野まで
○特定領域としての成果
・どんな集まりで、どんなアイデアが出て、どんな進展・研究があったか
どんなに細かいことでも良いので、事務局まで教えてほしい
○次の特定領域
・来年は、調査研究の申請をする
・そのために、今の特定領域で、領域として集まった成果を挙げる
成果報告書の執筆依頼
今年度の成果報告書を領域として作成する時期となりました．詳細は別途メール・ウェブで御連絡いたしますが，昨年度と同じ要領で，A01 から C11 の研究課題ごとに「研究活動報告」と「発表文献リスト」を御執筆いただけますようお願い申し上げます．なお，提出〆切は 3月31日(金) です．
http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/members/reports.html
旅費の補助
総括班予算より国際会議等の旅費の補助を行います。補助希望者は伊藤までお申し出ください。特に締め切りなどは設定しておりません。
・ジオメトリ合宿 (加藤直樹 浅野哲夫、徳山豪、David Avis)
2006年3月15日昼から17日まで
コミュニティ嵯峨野（京都府勤労者研修センター）（http://www.com-sagano.com/）
〒616-8372 京都市右京区嵯峨天龍寺広道町3-4
・COMP-NHC 学生シンポジウム (田中圭介)
2006年3月24日(金)〜26 日(日)のいずれか一日、国士舘大学世田谷キャンパス(東京都世田谷区)
電子情報通信学会 2006 年総合大会 シンポジウム講演 (B) DS-1 「COMP-NHC 学生シンポジウム」
(総合大会は2006年3月24(金)〜27(月))
3/27(月)-29(水) EWCG'06 (22nd European Symposium on Computational Geometry) Delphi, Greece
3/31(金)-4/2(日) Algebra and Combinatorics 2006 Manila, Philippines
4/24(月)-25(火) 第19回 回路とシステム軽井沢ワークショップ 軽井沢プリンスホテル西館
5/21(日)-23(火) STOC'06 Seattle, Washington, USA
6/5(月)-7(水) SoCG'06 Sedona, Arizona, USA
6/20(火)-22(木) The Second International Conference on Algorithmic Aspects in Information and Management 香港
6/22(木)-24(土) WG2006 (グラフアルゴリズムの会議です) ノルウェー，ベルゲン
6/25(日)-28(水) INFORMS International Hong Kong 2006 香港
7/3(月)-5(水) SIROCCO2006 Chester, United Kingdom
7/6(木)-8(土) SWAT 2006 リガ (ラトビア)
7/9(日)-16(日) ICALP 2006 ベネチア (イタリア)
7/30(日)-8/4(金) ISMP2006 Rio de Janeiro, Brazil
8/15(火)-18(金) COCOON 2006 台北（台湾）
8/22(火)-24(木) IFIP/TCS 2006 Santiago, Chile
9/11(月)-15(金) ALGO 2006 チューリッヒ (スイス)
ニュースレター各号は電子メールで配布する予定です．短い記事や連絡事項は全て掲載しますが，長い記事，イベントの詳細などはwebページに掲載する予定です．webページには詳細まで全てを載せた完全版を掲載して，目次，あるいは各記事の末尾のURLを参照すると，web版の同じ記事を参照できるようにいたします．
記事は，各回，１つの研究課題に担当をお願いする予定です．各研究課題で2000-4000字程度，研究に関わる記事を書いていただければと思います．通常，このようなニュースレターでは，研究成果を報告するのが一般的だと思われますが，この特定領域では「研究者の交流」に焦点を当てたいため，「研究の成果以外」の記事を面白く解説していただければと思います．例えば，最近参加した国際会議の情報を，どのようなものが流行っていたか，何が面白かったか，などの主観的な解説を交えて報告したり，最近考えている問題，あるいはオープン問題を，この辺までは解けるがここがうまくいかない，といった解説を交えて紹介する，という形です．
また，研究者間の交流を促進するため，各研究者の，国内外の会議への出席予定を集約して掲載していこうと考えています．研究者の交流には，顔をあわせる回数を増やすことが肝要です．他の研究者の参加予定がわかれば，会議への出席のモチベーションを高めることにもつながり，それがディスカッションや研究成果を生むきっかけにもなるでしょう．特定領域メンバーの皆さんには，自分のわかる範囲で，国内外の会議・研究会の情報と，自分の参加予定を教えていただければと思います．
この他，個人からの寄稿を募集いたします．100-1000字程度で，情報宣伝されたいことを自由な形式で書いて送っていただければ，掲載いたします．メールで配布する関係上，テキスト形式のものしか扱えませんが，そこはご了解お願いいたします．
次号は6月ごろを予定しています．
★ ニュースレター編集委員では，皆様からのご意見をお待ちしております．編集方針や内容の追加など編集全体にかかわることから細かいことまで，幅広いご意見をお願いいたします．
■■ 新世代の計算限界 ニュースレター ■■
編集委員長 宇野 毅明 uno@nii.jp (問合せ先)
副編集委員長 牧野 和久 makino@sflab.sys.es.osaka-u.ac.jp