Mercurial > hg > Papers > 2017 > ikkun-sigos
view mindmap.mm @ 31:aa067a010a3a
merge
author | ikkun |
---|---|
date | Tue, 16 May 2017 01:23:17 +0900 |
parents | f128810373f3 |
children |
line wrap: on
line source
<map version="1.0.1"> <!-- To view this file, download free mind mapping software FreeMind from http://freemind.sourceforge.net --> <node CREATED="1492595350085" ID="ID_1525898828" MODIFIED="1494759124518" TEXT="Gears OS における並列処理"> <font NAME="SansSerif" SIZE="16"/> <node CREATED="1492596047155" ID="ID_834413412" MODIFIED="1492599521160" POSITION="right" TEXT="研究目的"> <node CREATED="1492596132358" ID="ID_251539353" MODIFIED="1492596147777" TEXT="並列処理のプログラミングは信頼性の確保が難しい"> <node CREATED="1494759599699" ID="ID_1103318080" MODIFIED="1494759613270" TEXT="複雑さ"> <node CREATED="1494759614698" ID="ID_1336227916" MODIFIED="1494759622158" TEXT="パイプライン"/> <node CREATED="1494759623311" ID="ID_1116224711" MODIFIED="1494759630326" TEXT="データ並列化"/> <node CREATED="1494759632951" ID="ID_1512675661" MODIFIED="1494759636950" TEXT="通信"/> <node CREATED="1494759637815" ID="ID_608727346" MODIFIED="1494759640366" TEXT="同期"/> </node> </node> <node CREATED="1494759255320" ID="ID_377562133" MODIFIED="1494759280615" TEXT="並列処理のチューニングは難しい"> <node CREATED="1494759285616" ID="ID_464656512" MODIFIED="1494759414735" TEXT="アムダール則"/> <node CREATED="1494759380205" ID="ID_1115166650" MODIFIED="1494759426126" TEXT="テクノロジーマッピング"> <node CREATED="1494759430984" ID="ID_1519188342" MODIFIED="1494759439637" TEXT="GPGPU"/> <node CREATED="1494759440348" ID="ID_503355580" MODIFIED="1494759450686" TEXT="PCクラスタ"/> <node CREATED="1494759451887" ID="ID_1628193029" MODIFIED="1494759462694" TEXT="専用アーキテクチャ"/> </node> <node CREATED="1494759427167" ID="ID_530241215" MODIFIED="1494759516653" TEXT="Compiler directive"/> <node CREATED="1494759525506" ID="ID_611151551" MODIFIED="1494759533173" TEXT="MPI"/> <node CREATED="1494759537686" ID="ID_1866159972" MODIFIED="1494759545309" TEXT="CUDA"/> <node CREATED="1494759553412" ID="ID_1491842568" MODIFIED="1494759572271" TEXT="記述が煩雑"> <node CREATED="1494759572272" ID="ID_1036605218" MODIFIED="1494759589670" TEXT="すぐ時代遅れになる"/> </node> </node> <node CREATED="1494759664659" ID="ID_811317689" MODIFIED="1494759695118" TEXT="メタ計算を使った並列処理"> <node CREATED="1494759698395" ID="ID_282379188" MODIFIED="1494759735830" TEXT="チューニングをメタ計算部分で行う"/> <node CREATED="1494759737495" ID="ID_1418869704" MODIFIED="1494759884854" TEXT="信頼性の確保もメタ計算部分で行う"/> <node CREATED="1494759887127" ID="ID_402629690" MODIFIED="1494759912397" TEXT="アルゴリズムとチューニングを分離する"/> <node CREATED="1494759913724" ID="ID_786401208" MODIFIED="1494759940445" TEXT="メタ計算をサポートする言語CbCを扱う"/> <node CREATED="1494759941595" ID="ID_1342174865" MODIFIED="1494759974637" TEXT="コードとデータそれぞれにメタな部分がある"/> </node> <node CREATED="1492596119497" ID="ID_1681814830" MODIFIED="1492596130777" TEXT="Code Gear, Data Gear を使った並列処理"> <node CREATED="1492596155094" ID="ID_1650537256" MODIFIED="1492596171670" TEXT="Code Gear は Input された Data Gear 以外は触らない"/> <node CREATED="1492596173008" ID="ID_1062219126" MODIFIED="1492596201999" TEXT="Code Gear は実行内容を Output Data Gear に書き出す"/> <node CREATED="1492596205879" ID="ID_1257115080" MODIFIED="1492599432670" TEXT="Code Gear 間は継続処理でCode Gear を移動する"> <node CREATED="1492596261229" ID="ID_1766491596" MODIFIED="1492596271454" TEXT="基本的には末尾呼び出ししかつかえない"> <node CREATED="1492596233321" ID="ID_1043570655" MODIFIED="1492596258019" TEXT="functional な プログラミングスタイルを更に制約化する"/> </node> </node> <node CREATED="1492599312541" ID="ID_736319416" MODIFIED="1492599323077" TEXT="Input と Output の関係から並列処理を行う"/> <node CREATED="1492599411546" ID="ID_1634053755" MODIFIED="1492599421429" TEXT="Gode Gear "/> </node> <node CREATED="1492596298268" ID="ID_137287743" MODIFIED="1492596303427" TEXT="信頼性の確保"> <node CREATED="1492596303787" ID="ID_1118780576" MODIFIED="1492596308410" TEXT="モデルチェッキング"> <node CREATED="1492605188884" ID="ID_1336932146" MODIFIED="1492605199086" TEXT="single linked queue"/> <node CREATED="1492605200092" ID="ID_53892540" MODIFIED="1492605203422" TEXT="RB tree"/> </node> <node CREATED="1492596309380" ID="ID_1272495779" MODIFIED="1492596311353" TEXT="型チェック"/> <node CREATED="1492596313379" ID="ID_1955122588" MODIFIED="1492605181247" TEXT="検証"> <node CREATED="1492605181848" ID="ID_1919079450" MODIFIED="1492605187311" TEXT="並列処理の検証とか"/> </node> <node CREATED="1492605456922" ID="ID_182000760" MODIFIED="1492605460226" TEXT="どう嬉しいのか?"> <node CREATED="1492605492510" ID="ID_63268465" MODIFIED="1492605507032" TEXT="途中で止まらない"/> <node CREATED="1492605507626" ID="ID_283430344" MODIFIED="1492605517815" TEXT="整合性がちゃんと取れる"/> </node> </node> <node CREATED="1494761099227" ID="ID_1907135787" MODIFIED="1494761136298" TEXT="normal level"> <node CREATED="1494761138937" ID="ID_1784438052" MODIFIED="1494761158522" TEXT="継続で接続されたCode Gear"/> <node CREATED="1494761161057" ID="ID_527415358" MODIFIED="1494761184082" TEXT="input Data Gear と Output Data Gear"/> <node CREATED="1494761186594" ID="ID_417603619" MODIFIED="1494761217011" TEXT="Input と Output以外は触らない "> <node CREATED="1494761227424" ID="ID_403417067" MODIFIED="1494761233523" TEXT="ポインタはない"/> </node> <node CREATED="1494761241932" ID="ID_733410380" MODIFIED="1494761268907" TEXT="tail call のみを使う関数型プログラミング"> <node CREATED="1494761276236" ID="ID_715646781" MODIFIED="1494761288123" TEXT="agda に変換できる"/> <node CREATED="1494761290188" ID="ID_182846393" MODIFIED="1494761309003" TEXT="agda を使ってプログラムの正しさを証明したい"/> <node CREATED="1494761315025" ID="ID_34287223" MODIFIED="1494761328627" TEXT="ポインタ演算はメタ計算側で行う"> <node CREATED="1494761335849" ID="ID_579494470" MODIFIED="1494761344619" TEXT="例えばメモリ管理など"/> </node> </node> </node> <node CREATED="1492596730763" ID="ID_1218431096" MODIFIED="1494760391681" TEXT="meta computation"> <node CREATED="1492596742680" ID="ID_1927258639" MODIFIED="1492596762237" TEXT="実際に行う計算のための計算"> <node CREATED="1492596844936" ID="ID_365246262" MODIFIED="1492596865626" TEXT="network 間でversion 違う場合の整合性"/> <node CREATED="1492596763501" ID="ID_282207258" MODIFIED="1492596844321" TEXT="並列処理の依存関係"/> <node CREATED="1492598757212" ID="ID_1026249711" MODIFIED="1492598772215" TEXT="モデルチェッキングや検証"/> <node CREATED="1492599527749" ID="ID_1337410507" MODIFIED="1492599535142" TEXT="CPU, GPU の実行の切り替え"/> </node> <node CREATED="1492599338803" ID="ID_1764055121" MODIFIED="1492599390563" TEXT="Code Gearの接続間で meta Code Gear を用意し, そこで行う"> <node CREATED="1494760274310" ID="ID_244630254" MODIFIED="1494760328829" TEXT="Code Gear を管理する表"/> <node CREATED="1494760331766" ID="ID_1097458727" MODIFIED="1494760349132" TEXT="Code Gear の間に入るstub"/> <node CREATED="1494760350914" ID="ID_142372369" MODIFIED="1494760379812" TEXT="Code Gear の遷移を管理する Meta Code Gear"/> </node> <node CREATED="1494760121179" ID="ID_1341921987" MODIFIED="1494760169861" TEXT="Data Gear と Code Gear を管理する Meta Data Gear がある"> <node CREATED="1494760172638" ID="ID_1595517450" MODIFIED="1494760211076" TEXT="スレッドストラクチャーに相当するContext"/> <node CREATED="1494760228117" ID="ID_80626219" MODIFIED="1494760264045" TEXT="Context の管理を行うスケジューラ"/> </node> <node CREATED="1494760693133" ID="ID_1073090241" MODIFIED="1494760700587" TEXT="Interface"> <node CREATED="1494760704308" ID="ID_1070207889" MODIFIED="1494760730908" TEXT="Code Gear と Data Gear の集合"/> <node CREATED="1494760732517" ID="ID_394512662" MODIFIED="1494760779996" TEXT="Interface Data Gear を通してアクセスする"/> <node CREATED="1494760782333" ID="ID_1257836270" MODIFIED="1494760815036" TEXT="関数呼び出しのコールフレームに相当する"/> </node> <node CREATED="1494760582042" ID="ID_1517130971" MODIFIED="1494760600981" TEXT="CbCコンパイラ"> <node CREATED="1494760600982" ID="ID_1918147567" MODIFIED="1494760610113" TEXT="no stack frame"/> <node CREATED="1494760653220" ID="ID_551663297" MODIFIED="1494760681164" TEXT="メタ部分とノーマル部分を同じCbCで記述する"/> <node CREATED="1494760872680" ID="ID_1205279647" MODIFIED="1494760881709" TEXT="Gear box"> <node CREATED="1494760881710" ID="ID_79379372" MODIFIED="1494760915348" TEXT="GearsOS 用のステートチャートの拡張"/> </node> </node> <node CREATED="1494760620196" ID="ID_115694418" MODIFIED="1494760636460" TEXT="context の生成"> <node CREATED="1494761483268" ID="ID_362523788" MODIFIED="1494761508555" TEXT="使用するCode Gearの表"/> <node CREATED="1494761510408" ID="ID_1497583145" MODIFIED="1494761544331" TEXT="使用するData Gear の表と型の情報"/> <node CREATED="1494761546064" ID="ID_237438517" MODIFIED="1494761561331" TEXT="例外処理"/> <node CREATED="1494761569916" ID="ID_896829350" MODIFIED="1494761589619" TEXT="Data Gear の依存関係"/> <node CREATED="1494761591131" ID="ID_1495278711" MODIFIED="1494761598858" TEXT="メモリ管理"/> </node> <node CREATED="1494760637161" ID="ID_1185823918" MODIFIED="1494760648404" TEXT="stub の生成"> <node CREATED="1494761358048" ID="ID_537403430" MODIFIED="1494761424619" TEXT="Interface の Data Gear から必要なData Gear を抜き出して CbC のコードを呼び出す"/> <node CREATED="1494761426136" ID="ID_1765829055" MODIFIED="1494761476027" TEXT="引数をData Gear に書き出して Meta Code Gear に移行する"/> </node> </node> <node CREATED="1494760392909" ID="ID_40011244" MODIFIED="1494760407341" TEXT="従来技術"> <node CREATED="1494760409246" ID="ID_374552734" MODIFIED="1494760418956" TEXT="シンボルテーブル"/> <node CREATED="1494760420788" ID="ID_1365694917" MODIFIED="1494760444819" TEXT="dwarf format"/> <node CREATED="1494760446322" ID="ID_412266593" MODIFIED="1494760461411" TEXT="struct thread"/> <node CREATED="1494760462554" ID="ID_368691099" MODIFIED="1494760478523" TEXT="ABI"/> <node CREATED="1494760480152" ID="ID_1222061262" MODIFIED="1494760488003" TEXT="stack frame"/> <node CREATED="1494760490970" ID="ID_748291395" MODIFIED="1494760506403" TEXT="socket"/> <node CREATED="1494760507220" ID="ID_102243818" MODIFIED="1494760516987" TEXT="shared memory"/> <node CREATED="1494760517628" ID="ID_1661519236" MODIFIED="1494760520099" TEXT="CAS"/> <node CREATED="1494760524772" ID="ID_1771150593" MODIFIED="1494760551675" TEXT="semaphore/conditional wait"/> </node> <node CREATED="1492605323614" ID="ID_322917596" MODIFIED="1492605361854" TEXT="依存関係のある並列処理の設計"/> <node CREATED="1492605367168" ID="ID_1118914201" MODIFIED="1492605373124" TEXT="GPU での実行"/> </node> <node CREATED="1492596053460" ID="ID_1465968809" MODIFIED="1492596058101" POSITION="right" TEXT="Code Gear, Data Gear"> <node CREATED="1492599501735" ID="ID_271825383" MODIFIED="1492599504167" TEXT="いつもの話"/> </node> <node CREATED="1492596059830" ID="ID_1673128762" MODIFIED="1492596069427" POSITION="right" TEXT="Gears OSの構成"> <node CREATED="1492598873929" ID="ID_341820755" MODIFIED="1492598875273" TEXT="Context"> <node CREATED="1492599273720" ID="ID_1145032049" MODIFIED="1492599302246" TEXT="CG のリスト"/> <node CREATED="1492599280124" ID="ID_1742110158" MODIFIED="1492599304862" TEXT="DG のリスト"/> <node CREATED="1492599284153" ID="ID_1876844818" MODIFIED="1492599312025" TEXT="DG の allocate"/> <node CREATED="1492599605705" ID="ID_887878285" MODIFIED="1492599610261" TEXT="その他いろいろ"/> <node CREATED="1492599614820" ID="ID_1536135754" MODIFIED="1492599619148" TEXT="Task も Context"/> </node> <node CREATED="1492598864406" ID="ID_1687880423" MODIFIED="1492598866691" TEXT="TaskManager"> <node CREATED="1492599734061" ID="ID_653944383" MODIFIED="1492599741953" TEXT="Task Create"/> <node CREATED="1492599742553" ID="ID_647849311" MODIFIED="1492599747095" TEXT="Workers Create"/> <node CREATED="1492600814806" ID="ID_1329759540" MODIFIED="1492600824176" TEXT="Send Task to workers"/> <node CREATED="1492600828953" ID="ID_1336439792" MODIFIED="1492600843776" TEXT="set wait List for task"> <node CREATED="1492600846389" ID="ID_368998292" MODIFIED="1492600897116" TEXT="task"/> </node> </node> <node CREATED="1492598867265" ID="ID_1489374859" MODIFIED="1492598868395" TEXT="Worker"> <node CREATED="1492598880377" ID="ID_1745477396" MODIFIED="1492598921303" TEXT="Worker 毎に 実行するTaskが入っている synchronized queueをもつ"/> <node CREATED="1492598923368" ID="ID_114619867" MODIFIED="1492598937775" TEXT="TaskManager から task が sendされる"/> <node CREATED="1492598940541" ID="ID_353413891" MODIFIED="1492598945485" TEXT="実際にTaskを処理する"/> <node CREATED="1492603356876" ID="ID_1796895384" MODIFIED="1492603398977" TEXT="Task を処理した後, そのTaskで出力されたODS をcommit(依存関係の解決)する"/> </node> <node CREATED="1492598869771" ID="ID_970395828" MODIFIED="1492598873441" TEXT="Task(Context)"> <node CREATED="1492599612932" ID="ID_617828246" MODIFIED="1492599636562" TEXT="Task は Context として生成される"/> <node CREATED="1492599638427" ID="ID_1375136309" MODIFIED="1492599653963" TEXT="接続される idg の一覧"/> <node CREATED="1492599654300" ID="ID_1194751010" MODIFIED="1492599661731" TEXT="出力用の odg の一覧"/> <node CREATED="1492599664019" ID="ID_1727716436" MODIFIED="1492599692418" TEXT="持っている idg のカウント"/> </node> <node CREATED="1492605215716" ID="ID_1716718969" MODIFIED="1492605222054" TEXT="Rb_Tree(Jungle)"> <node CREATED="1492605222055" ID="ID_589981017" MODIFIED="1492605273760" TEXT="persistent な data を書き出す"/> <node CREATED="1492605282894" ID="ID_1687627848" MODIFIED="1492605286696" TEXT="この話する?"/> </node> <node CREATED="1494761026021" ID="ID_806096782" MODIFIED="1494761075014" TEXT="Context generator"/> <node CREATED="1494761058457" ID="ID_216232617" MODIFIED="1494761071277" TEXT="stub generator"/> </node> <node CREATED="1492596070507" ID="ID_1939634878" MODIFIED="1492603275648" POSITION="right" TEXT="依存関係の解決"> <node CREATED="1492601718132" ID="ID_1541948545" MODIFIED="1492604371573" TEXT="DG がそのDG を待っているtaskのqueueを持っている(wait List)"/> <node CREATED="1492604429601" ID="ID_1333930997" MODIFIED="1492604446500" TEXT="Output DG に書き込まれると, commit する "> <node CREATED="1492603275649" ID="ID_22296542" MODIFIED="1492603344062" TEXT="idgCount が0になると, 待っている input DG が用意できたので、taskを 実行するworker に sendする"/> <node CREATED="1492601759983" ID="ID_1738189652" MODIFIED="1492603066632" TEXT="Worker は Taskを実行した後, そのqueueを取り出し, TaskのidgCount をデクリメントする"/> </node> <node CREATED="1492604387355" ID="ID_339208879" MODIFIED="1492604418851" TEXT="Gears/doc/dependency.graffle 参照"/> </node> <node CREATED="1492596290291" ID="ID_71435553" MODIFIED="1492596291843" POSITION="right" TEXT="GPU"> <node CREATED="1492599486150" ID="ID_1589346879" MODIFIED="1492599494680" TEXT="いっくんの論文"/> <node CREATED="1492604042661" ID="ID_426423186" MODIFIED="1492604044280" TEXT="Cmake?"/> <node CREATED="1492604044696" ID="ID_968432973" MODIFIED="1492604050016" TEXT="CUDA Worker"/> </node> <node CREATED="1492599399002" ID="ID_1584696007" MODIFIED="1492599405083" POSITION="right" TEXT="並列実行のAPI"> <node CREATED="1492599406393" ID="ID_1396734805" MODIFIED="1492599408683" TEXT="par goto"> <node CREATED="1492599555831" ID="ID_14736352" MODIFIED="1492599591405" TEXT="main の createTaskでおこなっている idgや odg のセットなどをやってくれるAPI"/> <node CREATED="1492604154293" ID="ID_1555690452" MODIFIED="1492604262337" TEXT="par goto A->init(a); みたいな"> <node CREATED="1492604303376" ID="ID_738766443" MODIFIED="1492604354237" TEXT="詳しいはなしは Gears/src/parallel_execution/Todo に書かれてる"/> </node> </node> </node> <node CREATED="1492604097874" ID="ID_1082174010" MODIFIED="1492604101425" POSITION="right" TEXT="検証"> <node CREATED="1492604117017" ID="ID_446579225" MODIFIED="1492604141800" TEXT="multi thread の検証"> <node CREATED="1492604587774" ID="ID_379690336" MODIFIED="1492604600987" TEXT="CPU のクロックで時間を計測する"/> <node CREATED="1492604611684" ID="ID_25970880" MODIFIED="1492604627593" TEXT="Cerium はその方法で実測している"/> <node CREATED="1492605419779" ID="ID_1944953177" MODIFIED="1492605424675" TEXT="meta でいれる"/> </node> </node> <node CREATED="1492604701318" ID="ID_715646690" MODIFIED="1492605448994" POSITION="right" TEXT="今後の課題"> <node CREATED="1492604750945" ID="ID_1937336138" MODIFIED="1492604786954" TEXT="normal と meta levelの明示的な分離"/> <node CREATED="1492604705236" ID="ID_1476147969" MODIFIED="1492604813009" TEXT="multi thread で動いているかの検証をmeta 部分で行う"/> <node CREATED="1492604739017" ID="ID_591072804" MODIFIED="1492604808105" TEXT="並列実行APIの実装"/> </node> </node> </map>