完整後設資料紀錄
DC 欄位語言
dc.contributor.authorTIEN, JYen_US
dc.contributor.authorYANG, WPen_US
dc.date.accessioned2014-12-08T15:05:05Z-
dc.date.available2014-12-08T15:05:05Z-
dc.date.issued1991-12-01en_US
dc.identifier.issn0167-8191en_US
dc.identifier.urihttp://hdl.handle.net/11536/3627-
dc.description.abstractIncomplete hypercubes are gaining increasing attention as one of the possible solutions for the limitation on the number of nodes in the hypercubes. Distributing, in which one node sends distinct messages to distinct nodes, and its reverse operation are frequently used operations on data parallel computation. In this paper, we propose two types of spanning trees in incomplete hypercubes (composed of an n-cube and a k-cube): the binomial hierarchical spanning tree-binomial HST, and the balanced hierarchical spanning tree-balanced HST, for distributing (and its reverse operation). Distributing algorithms based on a balanced HST take better advantage of overlap between communication ports, or have speedup up to k/2 or n/2 over that based on the binomial HST when concurrently communication on all ports are possible, from the view point of communication complexity. An algorithm to construct hierarchical spanning trees in general incomplete hypercubes, which consist of an arbitrary number of nodes, is also devised.en_US
dc.language.isoen_USen_US
dc.subjectINCOMPLETE HYPERCUBESen_US
dc.subjectDISTRIBUTING, SPANNING TREESen_US
dc.subjectDATA COMMUNICATIONen_US
dc.titleHIERARCHICAL SPANNING-TREES AND DISTRIBUTING ON INCOMPLETE HYPERCUBESen_US
dc.typeArticleen_US
dc.identifier.journalPARALLEL COMPUTINGen_US
dc.citation.volume17en_US
dc.citation.issue12en_US
dc.citation.spage1343en_US
dc.citation.epage1360en_US
dc.contributor.department資訊科學與工程研究所zh_TW
dc.contributor.departmentInstitute of Computer Science and Engineeringen_US
dc.identifier.wosnumberWOS:A1991GV34200002-
dc.citation.woscount5-
顯示於類別:期刊論文