Search this article in Google Scholar


分類 国際会議
著者名 (author) Satoshi Fujita,Tadanori Nakagawa
英文著者名 (author)
編者名 (editor)
編者名 (英文)
キー (key)
表題 (title) Lower Bounding Techniques for the Multiprocessor Scheduling Problem with Communication Delay
表題 (英文)
書籍・会議録表題 (booktitle) Proc. International Conference on Parallel Architectures and Compilation Techniques (PACT)
書籍・会議録表題(英文)
巻数 (volume)
号数 (number)
ページ範囲 (pages) 212-220
組織名 (organization)
出版元 (publisher)
出版元 (英文)
出版社住所 (address)
刊行月 (month) October
出版年 (year) 1999
付加情報 (note) Newport Beach
注釈 (annote) DOI: 10.1109/PACT.1999.807534, Acceptance rate: 35/114 = 30%
内容梗概 (abstract) This paper proposes two techniques for obtaining a sharp lower bound for the multiprocessor scheduling problem (MSP) with nonnegligible communication delay. In the proposed techniques, we apply the notion of inevitable communication delay to obtain a nontrivial lower bound on the scheduling length. The effectiveness of the derived bound is evaluated by conducting experiments on several randomly generated instances. By the results of the experiments, it is shown that the proposed techniques generate a very sharp lower bound that is at least 97.5% of an upper bound, when the number of processors is not very small (e.g., at least 10) and the maximum communication cost is not very large (e.g., less than or equal to the minimum execution cost).
論文電子ファイル Not available.


[1-83]  Satoshi Fujita and Tadanori Nakagawa, ``Lower Bounding Techniques for the Multiprocessor Scheduling Problem with Communication Delay,'' In Proc. International Conference on Parallel Architectures and Compilation Techniques (PACT), pp. 212-220, October 1999. (Newport Beach)

@inproceedings{1_83,
    author = {Satoshi Fujita and Tadanori Nakagawa},
    author_e = {},
    editor = {},
    editor_e = {},
    title = {Lower Bounding Techniques for the Multiprocessor Scheduling Problem
    with Communication Delay},
    title_e = {},
    booktitle = {Proc. International Conference on Parallel Architectures and
    Compilation Techniques (PACT)},
    booktitle_e = {},
    volume = {},
    number = {},
    pages = {212-220},
    organization = {},
    publisher = {},
    publisher_e = {},
    address = {},
    month = {October},
    year = {1999},
    note = {Newport Beach},
    annote = {DOI: 10.1109/PACT.1999.807534, Acceptance rate: 35/114 = 30%}
}

This site is maintained by Distributed System Laboratory.

PMAN 2.5.5 - Paper MANagement system / (C) 2002-2008, Osamu Mizuno / All rights reserved.