{"created":"2025-01-18T23:04:20.448237+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00036182","sets":["1164:2836:2955:2958"]},"path":["2958"],"owner":"1","recid":"36182","title":["トーラス型マルチプロセッサシステム上での分枝限定アルゴリズム"],"pubdate":{"attribute_name":"公開日","attribute_value":"1988-05-20"},"_buckets":{"deposit":"a5f27c49-e805-4919-a0ad-49b85900bee9"},"_deposit":{"id":"36182","pid":{"type":"depid","value":"36182","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"トーラス型マルチプロセッサシステム上での分枝限定アルゴリズム","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"トーラス型マルチプロセッサシステム上での分枝限定アルゴリズム"},{"subitem_title":"A Parallel Branch -and- Bound Algorithm for a Torus Machine","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"1988-05-20","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"琉球大学工学部"},{"subitem_text_value":"琉球大学工学部"},{"subitem_text_value":"琉球大学工学部"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"University of the Ryukyus","subitem_text_language":"en"},{"subitem_text_value":"University of the Ryukyus","subitem_text_language":"en"},{"subitem_text_value":"University of the Ryukyus","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/36182/files/IPSJ-DPS88037012.pdf"},"date":[{"dateType":"Available","dateValue":"1990-05-20"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-DPS88037012.pdf","filesize":[{"value":"1.2 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"34"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"72e12641-7df2-43a3-acf7-3130da8c62be","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 1988 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"川口, 剛"},{"creatorName":"真栄田, 保"},{"creatorName":"喜屋武, 盛基"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tsuyoshi, Kawaguchi","creatorNameLang":"en"},{"creatorName":"Tamotsu, Maeda","creatorNameLang":"en"},{"creatorName":"Seiki, Kyan","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN10116224","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"トーラス型マルチプロセッサシステム上での並列分枝限定アルゴリズムを提案する。並列分技限定アルゴリズムに関する研究は、負荷分散手法の容易さのため、主に共有メモリ型システムに対して行われているが、このシステムは並列度に関して限界がある。一方、トーラス型システムは、木型システムと同様、高並列度を実現するのに適した構造をもつ。提案するアルゴリズムでは、部分問題を各プロセッサに均一に配分するための負荷分散手法が工夫されている。そして、ナップサック問題を用いた場合のシミュレーション結果から、本論文で提案するアルゴリズムの加速指数が、木型システムを改良したDONシステム（二重結合木型システム）に対する既存のアルゴリズムの加速指数より大きくなることが確かめろる。また、DONシステムに対するアルゴリズムと同様、問題の規模が大きくなるほど加速指数が増加し、しかも比較的計算時間を多く要す問題では加速指数がプロセッサの数より大きくなることが確かめられる。","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"In this paper we propose a parallel algorithm to execute branch-and-bound procedure on a torus machine with additional global links. The torus network is used when processors send subproblems to the respective adjacent processors in order to get a balanced work load. And global links are used for broadcasting the newly obtained temporary solution to all processors. Using the knapsack problem, the performance of the proposed algorithm is evaluated and is compared with the performance of a parallel brnch-and-bound algorithm for an improved tree machine.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"96","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告マルチメディア通信と分散処理（DPS）"}],"bibliographicPageStart":"89","bibliographicIssueDates":{"bibliographicIssueDate":"1988-05-20","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"35(1988-DPS-037)","bibliographicVolumeNumber":"1988"}]},"relation_version_is_last":true,"weko_creator_id":"1"},"id":36182,"updated":"2025-01-22T14:22:20.417619+00:00","links":{}}