Title
琉球大学ＨＤＬデザイン・コンテスト2000結果報告
Author(s)
和田, 知久; 翁長, 健治; 宮城, 隼夫; 吉田, たけお; 尾知, 博
Citation
琉球大学工学部紀要(60): 89-94
Issue Date
2000-09
URL
http://hdl.handle.net/20.500.12000/1431
Rights
琉球大学1』学部紀要第60号．2000年 8９
琉球大学ＨＤＬデザイン・コンテスト２０００結果報告
和田知久*、翁長健治**、宮城隼夫*、吉田たけお*、尾知博…UniversityoftheRyukyusHDLDesignContest2000Summary
rlbmohisaWada*,KenjiOnaga**,HayaoMiyagi*,THkeoYbshida*,andHimshiOchi**＊ AbstUPact UnivcrsitiesnationwidegatheredinOkinawa,Japan,onMarch3rdtoparticipateinUniversityoftheRyukyus lU)LDesignContest2000hostedbytheUniversityoftheRyukyus,DepartmentoflnfOmationEngineering・ Ofthel5applicants，tenfinalistswerechosenforthecontestwithtbeiroriginaldesignsonGaloisFieId mtrixmultiplierforRedundantArrayoflnexpensiveDisksSystem・ＡｐＩ口｣dandtrm〕hantteamofjuniors fromtheDepartmentoflnfomntionEngineeringattheUniversityoftheRyulq/uｓ（theteamTUrtlenecks"） wasawardedfirstprize，defeatingthemoreexperiencedMastersstudentsfromotheruniversities． KeyWbrds:ＨＤＬ,ＶＨＤＬ,VbrilogHDL,DesignOonbest 学部・高専部門と修士部門に分けて、それぞれの部門の ２チームに「めつちやはやいで餌（動作速度力塙速）と 「ちっちゃいで剛（回路規模が小さい）を授与し副賞と して各メンバーに３万円相当の賞品を授与しました．ま た､全10チームから最優秀チームを選び､｢最優秀償(シ ノプシス大賞)」を授与し副賞として各メンバーに５万円 相当の賞品を授与しました．また参加者全員にオリジナ ルＴシャツ（図１）を授与しました． 1．コンテスト概要 琉球大学では、日本シノプシス社のサポートによりハ ードウエア記述罰吾(VHDLまたはVbrilogHDL）を用 いたデザイン･コンテストを開催しました．コンテストは 今年度が３回目であり、今年度より琉球大学の学生だけ でなく、他大学や高等専門学校の学生も参加できるオー プンなコンテストにしました．オープン化初年度の本年 度はホームページ[1]によるデザイン・コンテストのＰＲ と主に口コミでの宣伝を行い､２月１８日の締切りまでに １５チーム（３０名）の学生達の参加がありました．事 前選考の結果、京大･阪大･九工大･豊田工業高等専門学校 より６チームの代表を沖縄に招待し、琉大の４チームと 合わせて､計10チームによる発表会を2000年３月３日 に琉球大学工学部にて行いました[２１１０チームを 受理：2000年６月２Ｇ日 *工学鋼間報工学科・ (DepLoflnfbrmationEng.,F歯cOfEngj 妙デジタル社会総合研究所 のigitalSocietyResemChInstitite） …九州工業大学砺子ｈｉ報工学科 (DepLofComputerSdBnceandEIectmnkSI､71旧yulnstituteoI mbchnology） 電子情報通信学会集稿回路研究会において平成12年５月発表済み 図ｌＴシャツ・デザイン和田・翁優・宮城・ilrIII・尾知：琉球入学IDLデザイン・コンテスト2000総来報!'「 9０ 込み保存しておきます．式（１）からＤＩＩ算と飛算力泌､要 とわかりますが、ガロア体で撹節を行うので、ガロア体 の加算はビットごとの排他的{総理fllとなり、采節はガIプ ア体での特殊な飛節となります．したがって、ガ１Ｊァ体 乗算器のi没,汁がひとつの識iii↑のキーポイントとなります． 2．コンテストの趣旨 SOC(システム・オン・チッカと喬われる大規模な集 積回路の実現力可能な今、ｄ指の爪のようなシリコン.チ ップに何千万ゲートからなる大規模なシステムが雄fl1i可 能です．マルチメディア・アイランドを|j指すiil1綱蝋に とっては､マルチメディアを支えるＫＥＹデバイスである． そのような超LSIシステム設計のできる人材育成に力を 入れ、ＶHDLを用いたデジタル設計･をjln常の,，淵'1の講溌 として提供しています[3]・コンテストの！]〔山は学'kjEに やや難易度とMMiI1のある諜題を９．えて、デザイン能ﾉﾉを 試すチャンスをｻﾞ.えることとliﾘIMFに、他の人'r:ﾍﾟ,AIjj<ｗ） 学生蝋と交流しiMi1fを広げることにあります． □凸イとへ、 ハレ【Ｕ、 【Ⅲ、叩ｎＭ０６『つ『ｊ 3．コンテストの設計課題／ポイント |Xl2RAIDシステム 今回の設計課題は「リードソロモンＣＯDEC用のガロ ァ体での行列乗算器の設計」です．リードソロモンはコ ンパクトディスクＣＤ）やデジタル通信･放送のエラー
訂正、ＲＡＩＤ（ＲＥdLmdantArrayofInexpensiveDisks〉
のような磁気ディスクの信頼性向上等の用途に１Wいられ ており、ガロア体という＃炉殊な代数での計算力泌要です．今回、データとしては４ビットの数値を取り扱い、アー
キテクチャと回路合成後の回路規模やクロックサイクル タイム、処理に必要なサイクル数、そして設計中のオリ ジナリティや工夫したポイントで設計結果を競いました． デジタル設計として有名なものにマイクロプロセッサがありますが、マイクロプロセッサ設計では設計対象と
アプリケーションのIMIにソフトウエアが介在し、デジタ
ル般計とアプリケーションの関係は希薄です.ＳＯＣとい
う時代では、アルゴリズムをチップ化（H/Ｗ化）すると
いうこと力溶易になり、重要になるということもあり今
回は通信等でポピュラーなリードソロモンという方式を
Ｈ/Ｗ化するという課題を選びました．リードソロモンＣＯDECと名前は難しそうですカミ今
回識十を行った演算器は次式に示される3入力1N1,1N2,
1N3迄3ｘ３の行列の行列乗算器で､各変数は４ビット幅
で華LJJLJ
鰯{菫(!'識議Ｍ㈹
この演算器をＲＡＩＤ（RedundantArrayof lnexpensiveDisks）というデータを記憶するハード･デ ィスクに冗長なチェック･サムを記憶するハード･ディス クを追加して信頼性をli1上した記憶システム（図２）を想定し動作検証を行います.データ入力、1,,2,,3から
式(2)にしたがってチェソクサムＣｌ,Ｃ2,Ｃ３を生成し、 Ｄ1,,2,,3,Ｃｌ,Ｃ2,Ｃ３をハード･ディスクに記憶します．|:}１１
催ﾄﾋﾞ
ｌｌ:ト，
】催ｌＭｌ
０１勺】 〔〃』へ二〔皇ｎＵ『』勺会 の (2) 図２のようにＤ2,,3,03のディスクが故障しデータが読み出せなくなった場合には､式（３）によりＤＬＣ１，０２
からオリジナルデータであるＤ1,,2,,3を再生成する
ことができます.（２）式の３ｘ３の行列はVandermonde行列であり、チェックサムの生成に用いられ、（３）式の
3ｘ３の行列はハード･ディスクの故障伏態により決定される行列です.したがって､同一の演算器を２個用いて、
異なった行列要素をあらかじめ設定することで、エンコ
ーダとデコーダを実現し、ＲＡＩＤ（図２）の入力データと
出力データが同じであることをチェックすることで検証
を行います．演算器には９つのアドレスを持つレジスタ・ファイル
ELE力泌要であり、３ｘ３の柿Ｉ要素をあらかじめ書き
琉｣:R大学'二学部紀要第60号，2000年 ノミｌ発表チームの設計のまとめ阪大「拝[I研 9１
阪大「谷口研」チーム、京大「ちよビット」チームがこ
のような構成でスピード重視の設計を行いました．琉大2年｢Ruo7｣ﾁｰﾑIRuo9｣ﾁｰﾑ､京大「〈
またいよう」チーム、九工大「ホークス」チームはガロ ア乗算器を３個用いて、OUT1,OUT2,OUT3を順次計 算する約３サイクルで計算を実行する方式を採用し､ス ピードと面積とも中庸の値を目指しました． 琉大３年「和田研」チーム、阪大「白川研」チームは ガロア体乗算器を１つのみ用いて、約９サイクルで計算 を実行する方式を採用し可面積最小を重視する設計を行 いました．1，
１I雪
３４０’|
’
６ ｢ ９．２２ －＿＿＿_＿」 ’５８９１１J
1－
'1
図３２サイクル動作の全体構成の例11451
’｜ ）４１|TI
４－２．ガロア乗算器の構成方法４ビットのガロア体はα4＋α＋１＝０（特性方程式と
いう）を満たすαを用いて、その４ビットを係数にもつ 以下のような３次の多項式に対応します．α].α3＋α,.αz＋α,.α'十α・…（４）
したがって、４ビットα3,αz,α1,ｑｏのガロア体の乗算
は（４）式で示される多項式の乗算となります．設計の
中`し課題のあるガロア体の乗算器は以下の３種類の方法
で実現されました．（１）「GFLOqGFILOGを用いる方法」
（２）「素直に多項式の乗算をする方法」
（３）「演算結果の表を用いる方聞ガロア乗算器として､GFLOG/GFILOGを用いる方法
を用いたチームの幾つかは､ガロア乗算器が9209､加蕊
gmog等の幾つかの処理ステージに分かれていることを
.；．.、.．.‐利用して､gnogの共通化等を行って回路面積削減を行っ
ています.ｶﾞﾛｱ体乗算には2つの9日.g力､jai宴でず縦
11|…
１．
両’
|Tｌ
4．参加行チームの設計結果レビュー ４－１．粁チームのアーキテクチャ設計の特徴各チームの設計の結果と特徴を喪ｌに示します．最も
蝋純な術成は（１）式である行列演算を同時に行う方式
で、’111路規模は大きくなりますが約１サイクルで冨攪を
完了できます．図３はガロア行列演算の出力をレジスタ
で受けて２サイクルで動作する構成例です．図の下方に
は９つの御l腰素ＥＩＥを保存するレジスタ･ファイルが
あります．発表を行った１０チーム中、豊田高専「仲野
研Ｃ」チーム、琉大３年「タートルネックス」チーム、
学校ｉ'ｉ チーム名 サィクル数 サイ クル 時間 ﾄーク ル 時間 面縦 特徴 １ 琉人２年 ＲＵＯ７ ３ 9.24 27.27 2739 gU０９６個 ９，０９３個 Adder3侭 ２ 琉人２年 ＲＵＯ９ ４ 219 87.〔1０ 2浬0 gflog4個 9,093個 Adder3個 ３ 豊田高専 仲野研Ｃ ２ 7.35 14.70 1203 簡略テーブル による乗算 ４ 琉大:1年 タートルネッ クス １ ３４０ 3.40 1205 素直な乗算器 9個 ５ 琉大３年 和(Ｉｌ研 ９ 7．３１ 65.79 743 素直な乗算器 1個 ６ 京大 〈またいよう ＩＢ 9.22 27.“ l麹０ ghog６個 蝉０９３個 Adder3m ７ ﾉL［大 ホークス （’ 5８９ 17.67 152】 gDog６個 9,093個 Adder3個 ８ 阪大 ﾈiL口研 ４ 1４．５ `１ 詔.16 BOO９１８個 9,099個 Adder9個 ９ 京大 ちよピント １ 2.40 2.4, 2413 素直な乗算器 9個 1０ 阪大 白ⅡＩ研 11 ６８７ 75.24 966 gUog1個 9ｍ０９１個 Ablder1個和田．翁長・宮城・吉田・尾知：琉球大学HDLデザイン・コンテスト2000結果報瞥 9２ ４－３．ＧFLOG/GFILOGを用いる方法 ガロア乗算器の１つの入力はレジスタ･ファイルである ので、レジスタ･ファイルに行列要素を書き込む再に
gUogにて変換された値をレジスタ･ファイルに保持する
ように設計し､ガロア乗算器から9,09回路を減らしてい ます． 結果からみると、GFLOG/GFILOGを用いる方法では なく、素直に多項式の乗算をする方法をもちいた方が回 路面積的にも、スピード的にも有利になっていました． 参加者の中には、設計した演算器を実際にＦＰＧＡに実 現し、画像データに対して、チェックサムに対1ｉｉｉIする画 像を生成し、そのチェヅクサム画像から源画像を復元す るデモをおこなうような面白いレポートもありました． 今回のデザイン・コンテストでは簡単のために、取り 扱うデータを４ビット幅と小さいものにしています．したがって､厳密には２４のｶﾞﾛｱ拡大体GF(24)を取り
扱います． この方法はデザイン･コンテストの参考文献とした JamesSPlankの論文Ｕで解説されている方法で､多く のチームがこの方式に従って乗算器を構成しました． 表２に示すように４ビットの２進数はそれぞれに多項式に対応します．今、特性方程式α４＋α＋ｌ＝０が成
立するので、この関係を用いて多項式を変形すると、２ 進数''0000''を除いてすべての多項式は α",(O≦〃≦14)という形式に変形できます． したがって、２つの多項式の乗算は以下のように指数 の通常の加算に変換することができます．(｡“?+`Ｍ；＋α1.0/+Qb）
×ｈｏ?+2h.ctz+4.α+々）
=ⅨIoglの.αぎ垣｡)＝α圏'ねgqHgnog(6)
表２ＧF(24)の２進数と多項式の関係
●●●⑥
また、粋性方程式α４＋α＋ｌ＝０よりα胸＝１である
ので､gnog(a)+9809(b)はmodl5（１５で割った余り）を 取ることにより、Ｏから１４の整数に丸めることができます．この値を8血ogの逆関数ghlogで変換すれば、ガロ
ア乗算の結果の４ビットの２進数を得ることができます．この方法では２進数，OOOOr，に力畑する指数は存在しま
せんので（あえて言えI鎖の無限大)、乗算入力の少なく
とも一方が２進数'００００，ならば、出力を２進数'0000,に
する必要があります．図４にこの方式のブロック図を示します.９８０９は４ビ
ット入力、４ビット出力の組み合わせ回路となり、ghlog
も同じく４ビット入力、４ビット出力の組み合わせ回路
となります．加算は通常の力噸であり、modl5は加算結
果が１５を超えた場合に１５の減算を行う回路です.Zem？
ブロックは入力の少なくとも１つの２進数'0000,,入力を
検知し、その場合は出力を強制的に２進数'00OOF，としま
す．､④
図４９，０９/gmogを用いたガロア乗算器
2進数 対応する多項式 1０進数 0000 ０ 0 0００１ 1＝ａ0 １ ００１０ α＝ａ ２ 0０１１ α＋ｌ＝ａ４ ３ ０１００ ａＺ ４ ０１０１αｚ＋１＝ａ
８ ５ ０１１０α２＋α＝ａ
５ ６ ０１１１α２＋α＋１＝ａ
10 ７ 1000 ａ３ ８ Ｊ１001α３＋ｌ＝ａ
1４ ９ 1010 ●ｗ－ａ３＋α＝ａ
９ 1０ 1０１１α３＋α＋１＝ａ
７ 1１ 1100α｣+αZ=ａ
６ 1２ 1１０１α］＋α２＋１＝ａ
1３ 1３ 1110α３＋α２＋α＝ａ
1１ 1４ 1111α]＋α２＋α＋１＝ａ
1２ 1５琉球人'ｻﾞ:l:学部紀要第60号．2000年 9３ 4-,1．素直に多項式の飛算をする方法 ツクサム画像から源画像を復元するデモを紹<介し注目を 集めていました（図５)． このﾉj式はガロア体のlvl:鷺に瓜って紫illlに計算する万 八です．デザイン・コンテストでは３つのチームがこの ,ｉｌｉ１:ﾉj法をillj↓Ｉ)して、結果li，によりシンプルで回路規模 の小きい乗鯨器を文jjMしました．２つの多項式を乗算す ると以下のようなります．
鼬駕
詳川
'二iｉ
Ｉｈｂｈｎ(qict1+妬･(f+〔ィo/＋`(1)仇ｃ（i+４㎡+ｎ.α+4〕）
=(MlJcf+(qr4“hJcf；
+但川①`ｈｈｅｑｒ４)α’
+(Ｍｂｅ`もムのａ向の“ぬ)α’
+(`zr4]のＭＩｅｑｒ４)o；
+(`J１．ｌｂ①q,･4)α+q)･&ｂ…（６）
｡戯琳 ＤＥＣＯＤＥｵｨｦit方程式α４＋α＋ｌ＝Ｏが成立するので､式(7a,7b'
7c）が成立します．α`＝α]＋α２…（7α）
αゴーα2＋α…（76）
α‘＝α＋ｌ…（7c）
図５「ちよビット」チームの画像デモ 阪大「白川剛チームは小面積を狙い11サイクルと いう長めの処理レイテンシではあるが、パイプライン処 理を行い９サイクルごとにデータの処理をできるように 実現しました． 琉大３年「和田研」チームは構成部品ごとの回路合成 後の回路規模を紹介し、種々の構成を検討した中での最 適解を求めたことを紹介しました．琉大３年「タミトル ネックス」チームはレジスタファイルなどにシフトレジ スタを適用することで、回路規模を削減できることを紹 介し注目を浴びていました． 豊田高専｢仲野研C｣チームは(3)｢槙i:i結果の表を用いる方脚でガロア演算を実現する時にJ(2:肘(3)
式の行列要素に５以下の整数値しｶﾖﾒiれな蝿篁激号着目し､演算結果の表を犬ｊ１高にii1iIili化しldNi薊鱗;高麹H2鍵
現しました．ここで、（7a7b,7c）式を用いて（６）式のα4以上の項
を３次以下の多項式に変形すると以下の(8)式のように なります．(必･茂+Q2．α2＋α｢α１＋q,)(6b,㎡＋ら,〆＋４．α'＋4）
=いもｂｅq2.6,＄α１．４①`J0.4鼬６５)α〕
+(喝・6ｂｅａＩｂｉｅ`】b･喝鋤･AeqT6h“.△)〆
+(Ｑ１ｔｂｅｃｌｂｂｉｅ`J3.6h“･４“･6ieqh･Ｑｅａ,･6b)α
+q０．４ｅらｆｊｉｅら･喝①α１．４…（８）
したがって、（８）式の各係数を計算することでガロア 体の乗算器が構成できます.結果的に､ＡＮＤゲート１６ 個とＸＯＲゲート１８でガロア体乗算器を構成すること ができました． 6．コンテストのまとめ結果的に学部･高専部門の琉大3年｢和田研｣チデムと
修士部門の阪大｢白111研｣チームが｢ちっちゃいで賞｣Ⅱ 面積）を獲得し、学部･高専部門で豊田高専｢仲野研C」チームと修士部門の京大「ちよビット」ﾁｰﾑﾄﾞが｢ぬっ
ちゃはやいで刺(高速･高性能)を１１篦得し、f最優秀賞(シ ノプシス大賞)」を琉大3年「タートルネック利チーム が他大学の修士学生らを抑えて獲得しました８今回の課題はガロア体という聞きなれなＭｂ数を実現
する必要があり、設計経験の少ない学生には振や困難な 5．課題にとらわれない工夫／発想 京大「ちよピット」チームは、設計した演算器を実際 にＦＰＧＡでPCIデバイスとして実現し､画像データに対 して、チェックサムに対応する画像を生成し、そのチエ9４ ｲ'１１１１．翁艇・1;｢城.，'；Ⅱｌ・ノfill：jjlt球人．.;:IH)しデ･リイン・コンテスト2ｌｘ)0ﾎﾟﾊﾙﾐ繩i1i しています．課題鞭はまだ|鮒''１であり、良いヒントが あればぜひ私のところまで教えて瓜ければ蟻いです[51． 琉球ﾉ〈`\:のあるilIIiWliは水l:から感虻的に遠く、このよ うなチャンスで学化･紋'１OIFの交流を深めることができ、」|； 常に有懲淀なイベントと綴えています．illl繩に遊びにＩ‘ たいというイ純な勅機も含めて伽Ⅲしますので、ドシド シ参加をおlliilいします． なお、このコンテストは''水シノプシス靴からの奨`.』ん 為:付余でサポートきｵしており、このような機会を1Ｊえて ［!いた'|本シノプシスイ|:にこのMliを(ｌｆ１)て深く感謝いた します． 内容であったようです．詩い換えれば､ＨＤＬによる設肘|・ 以前のｲ|さ様鮮fIWW1lのIjiif蛾が問かつたように感じます．し かしながら、`灘'１２年(kでも,没il･を光“たチームも多 数あり、コンテスト課題としてはやし)がいのある|ﾉ)群で あったと思います．このような1M雛な内存を実現した`?ｆ： '１KのiiM1足感を発炎から感じることができ、次ｲﾄﾞ度も「ぜ ひ参力l1したいｊという懲兇を多放の?it/|{から聞くことが できました． 発炎会で、$緋史アナログllLil路役!;|をｉｉにやっている阪 大「谷!]研」チームの'jﾒﾐﾉ|《より、行成ツールのi鯉やデ ジタルii難|のlliil'|善の感想ｌＡＩｊＩ１〈ことができ、彼[)にと 兎,てこのコンテストが#''１ｲIlLIikllだけでなく、技ilIiのIll1iを 1J;げＭ糊邑ｲ蝋施なものにな-Jたように,'11(います． 「１分j世と鴎な勺たアルゲプリズムで`ﾉﾐH1したチーム(/)うii jlil、微ｲＩして｢MViやＩＪＩ;能をIMjMi化したｲ|;卜のﾂﾞ.;:'１〈のがん ばり、ポ熱ある艦|津'|くらのハイプラインｌｉ;の岡1挺な｢Mlf iil･内容や発表会でのプレゼンテーシ曽]ンのｌｍさ、そし て池上ｻﾞ:／岡(11(との交流で、'ｻﾞ:'kI1ILで人きなjli'１激を受 けたようです． 研究会等では異なる各発炎鋤i異なる諜越について発 溌しますが、このような同一･の課題を異なる大学／,謝靭；（ の学4kが…蝋に会して発表会を持つことは、学'1洞この 大きな刺激とな})非常にｲi･効な機会でした（１）('６)． 参場klI1X
