分割統治法を用いたタスク並列Tree-based AMRアルゴリズム

河野, 瑛

WEKO3

AND

lat lon distance

[[sub_check.contents]]　

[[sub_radio.contents]]

Field does not validate

[[sub_attr.contents]]　

インデックスツリー

アイテム

{"_buckets": {"deposit": "7996ebdc-60fa-4e37-932a-3121049b473b"}, "_deposit": {"id": "4858", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "4858"}, "status": "published"}, "_oai": {"id": "oai:repository.dl.itc.u-tokyo.ac.jp:00004858"}, "item_7_alternative_title_1": {"attribute_name": "\u305d\u306e\u4ed6\u306e\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_alternative_title": "A Task Parallel Tree-based AMR Using Divide-and-Conquer Method"}]}, "item_7_biblio_info_7": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2013-03-25", "bibliographicIssueDateType": "Issued"}, "bibliographic_titles": [{}]}]}, "item_7_date_granted_25": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u5e74\u6708\u65e5", "attribute_value_mlt": [{"subitem_dategranted": "2013-03-25"}]}, "item_7_degree_name_20": {"attribute_name": "\u5b66\u4f4d\u540d", "attribute_value_mlt": [{"subitem_degreename": "\u4fee\u58eb(\u60c5\u5831\u7406\u5de5\u5b66)"}]}, "item_7_description_5": {"attribute_name": "\u6284\u9332", "attribute_value_mlt": [{"subitem_description": "\u5fae\u5206\u65b9\u7a0b\u5f0f\u306e\u6570\u5024\u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u306f\u5de5\u5b66\u30fb\u81ea\u7136\u79d1\u5b66\u7b49\u69d8\u3005\u306a\u5206\u91ce\u3067\u91cd\u8981\u306a\u554f\u984c\u3067\u3042\u308a\uff0c\u7279\u306b\u8fd1\u5e74\u4e26\u5217\u8a08\u7b97\u74b0\u5883\u3092\u7528\u3044\u305f\u5927\u898f\u6a21\u8a08\u7b97\u306b\u3088\u3063\u3066\u5927\u304d\u306a\u6210\u679c\u304c\u6319\u3052\u3089\u308c\u3066\u3044\u308b\uff0e\u3053\u308c\u3089\u306e\u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u306f\u4e00\u822c\u306b\u8a08\u7b97\u5bfe\u8c61\u7a7a\u9593\u3092\u683c\u5b50\u3092\u7528\u3044\u3066\u96e2\u6563\u5316\u3059\u308b\u3053\u3068\u3067\u884c\u308f\u308c\u308b\uff0e\u8a08\u7b97\u306e\u7cbe\u5ea6\u306f\u683c\u5b50\u306e\u30b5\u30a4\u30ba\u306b\u4f9d\u5b58\u3057\uff0c\u3088\u308a\u9ad8\u7cbe\u5ea6\u306a\u8a08\u7b97\u306b\u306f\u3088\u308a\u5927\u304d\u306a\u8a08\u7b97\u91cf\uff0c\u30c7\u30fc\u30bf\u30b5\u30a4\u30ba\u304c\u5fc5\u8981\u3068\u306a\u308b\uff0e\u3057\u304b\u3057\u306a\u304c\u3089\u591a\u304f\u306e\u5834\u5408\uff0c\u9ad8\u7cbe\u5ea6\u304c\u5fc5\u8981\u3068\u306a\u308b\u306e\u306f\u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u9818\u57df\u306e\u3054\u304f\u9650\u3089\u308c\u305f\u90e8\u5206\u3067\u3042\u308b\u3053\u3068\u304c\u591a\u304f\uff0c\u3053\u3046\u3044\u3063\u305f\u5834\u5408\u306b\u306f\u672c\u6765\u5fc5\u8981\u306e\u7121\u3044\u90e8\u5206\u306b\u307e\u3067\u7d30\u7c92\u5ea6\u306a\u683c\u5b50\u304c\u7528\u3044\u3089\u308c\u308b\u3053\u3068\u306b\u306a\u308b\uff0e\u3053\u306e\u3088\u3046\u306b\u9818\u57df\u4e2d\u306e\u5834\u6240\u306b\u3088\u3063\u3066\u6c42\u3081\u3089\u308c\u308b\u7cbe\u5ea6\u304c\u7570\u306a\u308b\u3088\u3046\u306a\u3044\u308f\u3086\u308b\u30de\u30eb\u30c1\u30b9\u30b1\u30fc\u30eb\u554f\u984c\u306b\u5bfe\u3057\u3066\u52b9\u679c\u3092\u767a\u63ee\u3059\u308b\u306e\u304cAdaptive Mesh Refinement(AMR) \u6cd5\u3067\u3042\u308b\uff0eAMR \u6cd5\u3067\u306f\u9ad8\u7cbe\u5ea6\u304c\u5fc5\u8981\u306a\u90e8\u5206\u306b\u5c40\u6240\u7684\u306b\u7d30\u304b\u3044\u683c\u5b50\u3092\u7528\u3044\u3066\u96e2\u6563\u5316\u3092\u884c\u3044\uff0c\u5168\u4f53\u306f\u7c97\u3044\u683c\u5b50\u3067\u96e2\u6563\u5316\u3092\u884c\u3046\u3053\u3068\u306b\u3088\u308a\uff0c\u8a08\u7b97\u91cf\u3084\u30e1\u30e2\u30ea\u91cf\u3092\u7bc0\u7d04\u3057\u3064\u3064\u9ad8\u89e3\u50cf\u5ea6\u306e\u8a08\u7b97\u3092\u5b9f\u73fe\u3059\u308b\uff0e\u7279\u306b\u9ad8\u7cbe\u5ea6\u304c\u5fc5\u8981\u306a\u90e8\u5206\u306b\u5bfe\u3057\u3066\u518d\u5e30\u7684\u306b\u7a7a\u9593\u3092\u5747\u7b49\u306b\u5206\u5272\u3059\u308b\u3053\u3068\u306b\u3088\u3063\u3066\u5f97\u3089\u308c\u308b\u683c\u5b50\u3092\u7528\u3044\u308bTree-based AMR \u6cd5\u306b\u5bfe\u3057\u3066\uff0c\u8fd1\u5e74\u5927\u898f\u6a21\u306a\u4e26\u5217\u8a08\u7b97\u3092\u884c\u3046\u7814\u7a76\u304c\u76db\u3093\u306b\u884c\u308f\u308c\u3066\u3044\u308b\uff0eTree-based AMR \u6cd5\u306f\u7a7a\u9593\u7684\u306b\u4e0d\u5747\u4e00\u306a\u30c7\u30fc\u30bf\u5206\u5e03\u3092\u6301\u3061\uff0c\u307e\u305f\u8a08\u7b97\u304c\u9032\u3080\u306b\u9023\u308c\u3066\u683c\u5b50\u304c\u5909\u5316\u3057\u3066\u3044\u304f\u305f\u3081\u306b\uff0c\u5f93\u6765\u7528\u3044\u3089\u308c\u3066\u304d\u305f\u3088\u3046\u306a\u30c7\u30fc\u30bf\u3092\u5206\u8f44\u3059\u308b\u3053\u3068\u306b\u3088\u3063\u3066\u4e26\u5217\u5316\u3092\u884c\u3046SPMD \u30e2\u30c7\u30eb\u3092\u7528\u3044\u3066\u52b9\u7387\u7684\u306a\u4e26\u5217\u30d7\u30ed\u30b0\u30e9\u30e0\u3092\u8a18\u8ff0\u3059\u308b\u3053\u3068\u306f\u96e3\u3057\u3044\u554f\u984c\u3067\u3042\u308b\uff0e\u4e00\u65b9\u3067\u3053\u306e\u3088\u3046\u306a\u4e26\u5217\u5316\u306e\u96e3\u3057\u3044\u30a2\u30d7\u30ea\u30b1\u30fc\u30b7\u30e7\u30f3\u3084\u968e\u5c64\u5316\u30fb\u8907\u96d1\u5316\u306e\u9032\u3080\u8a08\u7b97\u6a5f\u74b0\u5883\u3092\u80cc\u666f\u306b\uff0c\u9ad8\u751f\u7523\u306b\u4e26\u5217\u8a08\u7b97\u3092\u884c\u3046\u3053\u3068\u304c\u3067\u304d\u308b\u4e26\u5217\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u30e2\u30c7\u30eb\u3084\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u8a00\u8a9e\u3078\u306e\u8981\u8acb\u304c\u9ad8\u307e\u3063\u3066\u3044\u308b\uff0e\u4e2d\u3067\u3082\u30bf\u30b9\u30af\u4e26\u5217\u30e2\u30c7\u30eb\u306f\uff0c\u30d7\u30ed\u30b0\u30e9\u30e0\u4e2d\u306e\u4efb\u610f\u306e\u5834\u6240\u3067\u751f\u6210\u3067\u304d\u308b\u4e26\u5217\u5b9f\u884c\u53ef\u80fd\u306a\u300e\u30bf\u30b9\u30af\u300f\u3092\u7528\u3044\u305f\u67d4\u8edf\u306a\u4e26\u5217\u6027\u306e\u8a18\u8ff0\u304c\u53ef\u80fd\u3067\u3042\u308a\uff0c\u7279\u306b\u518d\u5e30\u3092\u7528\u3044\u308b\u5206\u5272\u7d71\u6cbb\u6cd5\u306e\u3088\u3046\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3082\u76f4\u611f\u7684\u304b\u3064\u52b9\u7387\u7684\u306b\u4e26\u5217\u5316\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u308b\uff0e\u307e\u305f\uff0c\u51e6\u7406\u7cfb\u306b\u3088\u3063\u3066\u81ea\u52d5\u7684\u306b\u8a08\u7b97\u30d7\u30ed\u30bb\u30b9\u9593\u306e\u8ca0\u8377\u5206\u6563\u304c\u304a\u3053\u306a\u308f\u308c\u308b\u305f\u3081\uff0c\u52d5\u7684\u306a\u30a2\u30d7\u30ea\u30b1\u30fc\u30b7\u30e7\u30f3\u306b\u5bfe\u3057\u3066\u3082\u52b9\u7387\u7684\u306a\u4e26\u5217\u5316\u304c\u53ef\u80fd\u3067\u3042\u308b\uff0e\u672c\u7814\u7a76\u3067\u306f\u3053\u306e\u3088\u3046\u306a\u80cc\u666f\u304b\u3089\uff0c\u30bf\u30b9\u30af\u4e26\u5217\u30e2\u30c7\u30eb\u3092\u7528\u3044\u305fTree-based AMR \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u63d0\u6848\u3057\u3066\u3044\u308b\uff0e\u63d0\u6848\u624b\u6cd5\u3067\u306f\uff0c\u30bf\u30b9\u30af\u4e26\u5217\u51e6\u7406\u7cfb\u306b\u3088\u308b\u81ea\u52d5\u7684\u306a\u8ca0\u8377\u5206\u6563\u3084\u898b\u901a\u3057\u306e\u826f\u3044\u4e26\u5217\u5316\u3092\u5b9f\u73fe\u3057\u3066\u3044\u308b\u3060\u3051\u3067\u306a\u304f\uff0c\u5206\u5272\u7d71\u6cbb\u6cd5\u306b\u57fa\u3065\u3044\u305f\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3088\u308a\u52b9\u7387\u7684\u306a\u51e6\u7406\u3092\u53ef\u80fd\u306b\u3057\u3066\u3044\u308b\uff0e\u7279\u306b\u683c\u5b50\u4e2d\u306e\u96a3\u63a5\u30bb\u30eb\u3078\u306e\u30a2\u30af\u30bb\u30b9\u3092\u4f34\u3046\u3088\u3046\u306a\u64cd\u4f5c\u306b\u5bfe\u3057\u3066\u306f\uff0c\u5f93\u6765\u5168\u4f53\u3067O(n log(n)) \u306e\u8a08\u7b97\u30b3\u30b9\u30c8\u3092\u8981\u3059\u308b\u304b\uff0c\u3082\u3057\u304f\u306f\u9ad8\u901f\u5316\u306e\u305f\u3081\u306e\u30c7\u30fc\u30bf\u69cb\u9020\u3092\u5225\u306b\u7528\u610f\u3059\u308b\u5fc5\u8981\u304c\u3042\u3063\u305f\u306e\u306b\u5bfe\u3057\u3066\uff0c\u6728\u69cb\u9020\u306e\u30c7\u30fc\u30bf\u5206\u6563\u304c\u504f\u308a\u3059\u304e\u3066\u3044\u306a\u3044\u3068\u3044\u3046\u524d\u63d0\u306e\u3082\u3068\u3067\u30b7\u30f3\u30d7\u30eb\u306a\u30c7\u30fc\u30bf\u69cb\u9020\u3092\u4fdd\u3061\u306a\u304c\u3089O(n) \u306e\u8a08\u7b97\u30b3\u30b9\u30c8\u3092\u5b9f\u73fe\u3057\u3066\u3044\u308b\uff0e\u5b9f\u969b\u306b\uff0c\u79fb\u6d41\u65b9\u7a0b\u5f0f\u3068\u62e1\u6563\u65b9\u7a0b\u5f0f\u306e\u5dee\u5206\u89e3\u6cd5\u306b\u57fa\u3065\u3044\u305fTree-based AMR \u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u306e\u5b9f\u88c5\u3092\u884c\u3044\u5171\u6709\u30e1\u30e2\u30ea\u74b0\u5883\u3067\u826f\u597d\u306a\u4e26\u5217\u6027\u80fd\u3092\u78ba\u8a8d\u3057\u305f\uff0e", "subitem_description_type": "Abstract"}]}, "item_7_full_name_3": {"attribute_name": "\u8457\u8005\u5225\u540d", "attribute_value_mlt": [{"nameIdentifiers": [{"nameIdentifier": "10556", "nameIdentifierScheme": "WEKO"}], "names": [{"name": "Kono, Akira"}]}]}, "item_7_select_21": {"attribute_name": "\u5b66\u4f4d", "attribute_value_mlt": [{"subitem_select_item": "master"}]}, "item_7_text_24": {"attribute_name": "\u7814\u7a76\u79d1\u30fb\u5c02\u653b", "attribute_value_mlt": [{"subitem_text_value": "\u60c5\u5831\u7406\u5de5\u5b66\u7cfb\u7814\u7a76\u79d1\u30fb\u96fb\u5b50\u60c5\u5831\u5b66\u5c02\u653b"}]}, "item_7_text_36": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"subitem_text_value": "Thesis"}]}, "item_7_text_4": {"attribute_name": "\u8457\u8005\u6240\u5c5e", "attribute_value_mlt": [{"subitem_text_value": "\u6771\u4eac\u5927\u5b66\u5927\u5b66\u9662\u60c5\u5831\u7406\u5de5\u5b66\u7cfb\u7814\u7a76\u79d1\u96fb\u5b50\u60c5\u5831\u5b66\u5c02\u653b"}, {"subitem_text_value": "Department of Information and Communication Engineering, Graduate School of Information Science and Technology, The University of Tokyo"}]}, "item_creator": {"attribute_name": "\u8457\u8005", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "\u6cb3\u91ce, \u745b"}], "nameIdentifiers": [{"nameIdentifier": "10555", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "\u30d5\u30a1\u30a4\u30eb\u60c5\u5831", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2017-06-01"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "48116422.pdf", "filesize": [{"value": "2.7 MB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 2700000.0, "url": {"label": "48116422.pdf", "url": "https://repository.dl.itc.u-tokyo.ac.jp/record/4858/files/48116422.pdf"}, "version_id": "92537ab6-1f9e-4a0b-8fe0-2a3877286676"}]}, "item_language": {"attribute_name": "\u8a00\u8a9e", "attribute_value_mlt": [{"subitem_language": "jpn"}]}, "item_resource_type": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"resourcetype": "thesis", "resourceuri": "http://purl.org/coar/resource_type/c_46ec"}]}, "item_title": "\u5206\u5272\u7d71\u6cbb\u6cd5\u3092\u7528\u3044\u305f\u30bf\u30b9\u30af\u4e26\u5217Tree-based AMR\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "\u5206\u5272\u7d71\u6cbb\u6cd5\u3092\u7528\u3044\u305f\u30bf\u30b9\u30af\u4e26\u5217Tree-based AMR\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0"}]}, "item_type_id": "7", "owner": "1", "path": ["9/233/234", "34/105/262"], "permalink_uri": "http://hdl.handle.net/2261/54203", "pubdate": {"attribute_name": "\u516c\u958b\u65e5", "attribute_value": "2013-05-07"}, "publish_date": "2013-05-07", "publish_status": "0", "recid": "4858", "relation": {}, "relation_version_is_last": true, "title": ["\u5206\u5272\u7d71\u6cbb\u6cd5\u3092\u7528\u3044\u305f\u30bf\u30b9\u30af\u4e26\u5217Tree-based AMR\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0"], "weko_shared_id": null}

分割統治法を用いたタスク並列Tree-based AMRアルゴリズム

http://hdl.handle.net/2261/54203

	名前 / ファイル	ライセンス	アクション
	48116422.pdf (2.7 MB)

Item type

学位論文 / Thesis or Dissertation(1)

公開日

2013-05-07

タイトル

分割統治法を用いたタスク並列Tree-based AMRアルゴリズム

言語

jpn

資源タイプ

資源

http://purl.org/coar/resource_type/c_46ec

タイプ

thesis

その他のタイトル

A Task Parallel Tree-based AMR Using Divide-and-Conquer Method

著者

河野, 瑛

著者別名

識別子

10556

識別子Scheme

WEKO

姓名

Kono, Akira

著者所属

東京大学大学院情報理工学系研究科電子情報学専攻

著者所属

Department of Information and Communication Engineering, Graduate School of Information Science and Technology, The University of Tokyo

Abstract

内容記述タイプ

Abstract

内容記述

微分方程式の数値シミュレーションは工学・自然科学等様々な分野で重要な問題であり，特に近年並列計算環境を用いた大規模計算によって大きな成果が挙げられている．これらのシミュレーションは一般に計算対象空間を格子を用いて離散化することで行われる．計算の精度は格子のサイズに依存し，より高精度な計算にはより大きな計算量，データサイズが必要となる．しかしながら多くの場合，高精度が必要となるのはシミュレーション領域のごく限られた部分であることが多く，こういった場合には本来必要の無い部分にまで細粒度な格子が用いられることになる．このように領域中の場所によって求められる精度が異なるようないわゆるマルチスケール問題に対して効果を発揮するのがAdaptive Mesh Refinement(AMR) 法である．AMR 法では高精度が必要な部分に局所的に細かい格子を用いて離散化を行い，全体は粗い格子で離散化を行うことにより，計算量やメモリ量を節約しつつ高解像度の計算を実現する．特に高精度が必要な部分に対して再帰的に空間を均等に分割することによって得られる格子を用いるTree-based AMR 法に対して，近年大規模な並列計算を行う研究が盛んに行われている．Tree-based AMR 法は空間的に不均一なデータ分布を持ち，また計算が進むに連れて格子が変化していくために，従来用いられてきたようなデータを分轄することによって並列化を行うSPMD モデルを用いて効率的な並列プログラムを記述することは難しい問題である．一方でこのような並列化の難しいアプリケーションや階層化・複雑化の進む計算機環境を背景に，高生産に並列計算を行うことができる並列プログラミングモデルやプログラミング言語への要請が高まっている．中でもタスク並列モデルは，プログラム中の任意の場所で生成できる並列実行可能な『タスク』を用いた柔軟な並列性の記述が可能であり，特に再帰を用いる分割統治法のようなアルゴリズムも直感的かつ効率的に並列化することができる．また，処理系によって自動的に計算プロセス間の負荷分散がおこなわれるため，動的なアプリケーションに対しても効率的な並列化が可能である．本研究ではこのような背景から，タスク並列モデルを用いたTree-based AMR アルゴリズムを提案している．提案手法では，タスク並列処理系による自動的な負荷分散や見通しの良い並列化を実現しているだけでなく，分割統治法に基づいたアルゴリズムにより効率的な処理を可能にしている．特に格子中の隣接セルへのアクセスを伴うような操作に対しては，従来全体でO(n log(n)) の計算コストを要するか，もしくは高速化のためのデータ構造を別に用意する必要があったのに対して，木構造のデータ分散が偏りすぎていないという前提のもとでシンプルなデータ構造を保ちながらO(n) の計算コストを実現している．実際に，移流方程式と拡散方程式の差分解法に基づいたTree-based AMR シミュレーションの実装を行い共有メモリ環境で良好な並列性能を確認した．

書誌情報

発行日 2013-03-25

学位名

修士(情報理工学)

学位

値

master

研究科・専攻

情報理工学系研究科・電子情報学専攻

学位授与年月日

2013-03-25

戻る

views

See details

	Views

Versions

Ver.1

2021-03-02 07:49:06.093209

Show All versions

Cite as

Export

OAI-PMH

JPCOAR
DublinCore
DDI

Other Formats

JSON
BIBTEX

インデックスリンク

インデックスツリー

アイテム

分割統治法を用いたタスク並列Tree-based AMRアルゴリズム

× 河野, 瑛

Versions

Share

Cite as

Export