DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lee, H | - |
dc.contributor.author | Kim, J | - |
dc.contributor.author | Hong, SJ | - |
dc.contributor.author | Lee, S | - |
dc.date.accessioned | 2016-03-31T12:52:17Z | - |
dc.date.available | 2016-03-31T12:52:17Z | - |
dc.date.created | 2009-02-28 | - |
dc.date.issued | 2003-04 | - |
dc.identifier.issn | 1045-9219 | - |
dc.identifier.other | 2003-OAK-0000003322 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/18590 | - |
dc.description.abstract | The problem of finding an optimal product sequence for sequential multiplication of a chain of. matrices (the matrix chain ordering problem, MCOP) is well-known and has been studied for a long time. In this paper, we consider the, problem of finding an optimal product schedule for evaluating a chain of matrix products on a parallel computer (the matrix chain scheduling problem, MCSP). The difference between the MCSP and the MCOP is that the MCOP pertains to a product sequence for single processor systems and the MCSP pertains to a sequence of concurrent matrix products for parallel systems. The approach of parallelizing each matrix product after finding an optimal product sequence for single processor systems does not always guarantee the minimum evaluation time-on parallel systems since each parallelized matrix product may use processors inefficiently. We introduce a new processor scheduling algorithm for the MCSP which reduces the evaluation time of a chain of matrix products on a parallel. computer, even at the expense of a slight increase in the total number of operations. Given a chain of n matrices and a matrix product utilizing at most P/k processors in a P-processor system, the proposed algorithm approaches k(n - 1)/(n + k log(k) - k) times the performance of parallel evaluation using the optimal sequence found for the MCOP. Also, experiments performed on a Fujitsu AP1000 multicomputer show that the proposed algorithm significantly decreases the time required to evaluate a chain of matrix,products in parallel systems. | - |
dc.description.statementofresponsibility | X | - |
dc.language | English | - |
dc.publisher | IEEE-INST ELECTRICAL ELECTRONICS ENGI | - |
dc.relation.isPartOf | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | - |
dc.subject | matrix chain product | - |
dc.subject | parallel matrix multiplication | - |
dc.subject | matrix chain scheduling problem | - |
dc.subject | processor allocation | - |
dc.subject | task scheduling | - |
dc.subject | APPROXIMATION | - |
dc.subject | COMPUTATION | - |
dc.subject | ALGORITHMS | - |
dc.title | Processor allocation and task scheduling of matrix chain products on parallel system | - |
dc.type | Article | - |
dc.contributor.college | 컴퓨터공학과 | - |
dc.identifier.doi | 10.1109/TPDS.2003.1195411 | - |
dc.author.google | Lee, H | - |
dc.author.google | Kim, J | - |
dc.author.google | Hong, SJ | - |
dc.author.google | Lee, S | - |
dc.relation.volume | 14 | - |
dc.relation.issue | 4 | - |
dc.relation.startpage | 394 | - |
dc.relation.lastpage | 407 | - |
dc.contributor.id | 10074421 | - |
dc.relation.journal | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | - |
dc.relation.index | SCI급, SCOPUS 등재논문 | - |
dc.relation.sci | SCI | - |
dc.collections.name | Journal Papers | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, v.14, no.4, pp.394 - 407 | - |
dc.identifier.wosid | 000182162900005 | - |
dc.date.tcdate | 2019-01-01 | - |
dc.citation.endPage | 407 | - |
dc.citation.number | 4 | - |
dc.citation.startPage | 394 | - |
dc.citation.title | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | - |
dc.citation.volume | 14 | - |
dc.contributor.affiliatedAuthor | Kim, J | - |
dc.contributor.affiliatedAuthor | Lee, S | - |
dc.identifier.scopusid | 2-s2.0-0037619247 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.wostc | 15 | - |
dc.type.docType | Article | - |
dc.subject.keywordPlus | APPROXIMATION | - |
dc.subject.keywordPlus | COMPUTATION | - |
dc.subject.keywordPlus | ALGORITHMS | - |
dc.subject.keywordAuthor | matrix chain product | - |
dc.subject.keywordAuthor | parallel matrix multiplication | - |
dc.subject.keywordAuthor | matrix chain scheduling problem | - |
dc.subject.keywordAuthor | processor allocation | - |
dc.subject.keywordAuthor | task scheduling | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Theory & Methods | - |
dc.relation.journalWebOfScienceCategory | Engineering, Electrical & Electronic | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Engineering | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.