article

Free access

Access conflicts in multiprocessor memories queueing models and simulation studies

Authors:

Ingrid Y. Bucher,

Donald A. CalahanAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 18, Issue 3b

Pages 428 - 438

https://doi.org/10.1145/255129.255184

Published: 01 June 1990 Publication History

PDF eReader

Abstract

The performance of an interleaved common memory accessed uniformly by multiple processors is modeled by queueing methods. The model includes access conflicts at the bank level while assuming an ideal access network.

A scaling relation is derived that is generally valid and indicates that memory access delays are given by the product of the bank reservation time and a function of the memory utilization, which is given by the average number of access requests arriving at a bank per bank reservation time. For light memory traffic, access delays are proportional to the square of the bank reservation time and the ratio of the number of active memory access streams to the number of memory banks.

Assuming random access patterns, an open and a closed queueing model are developed that are validated by simulations. Delay dependence on bank reservation time is quadratic for light loads and linear for very heavy loads.

A heuristic extension of our model for vector accessing of banks in sequential mode is proposed.

References

[1]

Calahan, D. A. and D. H. Bailey, "'Measurement and Analysis of Memory Conflicts on Vector Multiprocessors," in Performance Evaluation of Supercomputers, J. L. Martin, Ed., Elsevier, 1988.

Google Scholar

[2]

Bucher, I. Y. and M. L. Simmons, "Measurements of Memory Access Contentions in Multiple Vector Proeessor Systems," to be published.

Google Scholar

[3]

Chang, D. Y., D. J. Kuck, and D. H. Lawrie, "On the Effective Bandwidth of Parallel Memories," IEEE Trans. Comp., C-26 (1977), 480-489.

Digital Library

Google Scholar

[4]

Bailey, D. H., "Vector Computer Memory Bank Contention," IEEE Trans. Comp., C-36 (1987), 293-298.

Digital Library

Google Scholar

[5]

Calahan, D. A. "Some Results in Memory Conflict Analysis," Proceedings of Supercomputing 1989, 775-778.

Digital Library

Google Scholar

[6]

Tang, P. and R. H. Mendez, "Memory Conflicts and Machine Performance," Proceedings of Supercomputing 1989, 826-831.

Digital Library

Google Scholar

[7]

Denning, P. J. and J. P. Buzen, "The Operational Analysis of Queueing Network Models," Computing Surveys 10 (1978), 225-261.

Digital Library

Google Scholar

[8]

Kleinrock, L., "Queueing Theory," Vol. i, Wiley, New York, 1975.

Google Scholar

Cited By

View all

Xu DChu CLiu CWang YZhou XZhang LLiang HLi HMohsenin TZhao WChen YMutlu O(2020)Multi-task Scheduling for PIM-based Heterogeneous Computing SystemProceedings of the 2020 on Great Lakes Symposium on VLSI10.1145/3386263.3406946(457-462)Online publication date: 7-Sep-2020
https://dl.acm.org/doi/10.1145/3386263.3406946
Pang DXu DWang YLiang H(2018)MTTF-Aware Reliability Task Scheduling for PIM-Based Heterogeneous Computing System2018 IEEE International Test Conference in Asia (ITC-Asia)10.1109/ITC-Asia.2018.00015(25-30)Online publication date: Aug-2018
https://doi.org/10.1109/ITC-Asia.2018.00015
Friedman AFriedman A(1992)Interprocessor memory contentionMathematics in Industrial Problems10.1007/978-1-4615-7405-7_11(112-121)Online publication date: 1992
https://doi.org/10.1007/978-1-4615-7405-7_11
Show More Cited By

Index Terms

Access conflicts in multiprocessor memories queueing models and simulation studies

Recommendations

Access conflicts in multiprocessor memories queueing models and simulation studies
ICS '90: Proceedings of the 4th international conference on Supercomputing

The performance of an interleaved common memory accessed uniformly by multiple processors is modeled by queueing methods. The model includes access conflicts at the bank level while assuming an ideal access network.

A scaling relation is derived that is ...
Models of Access Delays in Multiprocessor Memories

The performance of an interleaved common memory accessed uniformly by multiple processors is modeled by queuing and simulation methods. The model includes access conflicts at the bank level while assuming an ideal access network. A general scaling law ...
Role-Based Access Control Models

Since the 1970s, computer systems have featured multiple applications and served multiple users, leading to heightened awareness of data security issues. System administrators and software developers focused on different kinds of access control to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 18, Issue 3b

Special Issue: Proceedings of the 4th international conference on Supercomputing

Sept. 1990

489 pages

ISSN:0163-5964

DOI:10.1145/255129

Chairmen:
Ahmed Sameh
Univ. of Illinois at Urbana-Champaign, Urbana
,
Henk van der Vorst
Delft Univ. of Technology and CWI, The Netherlands

Issue’s Table of Contents

ICS '90: Proceedings of the 4th international conference on Supercomputing
June 1990
492 pages
ISBN:0897913698
DOI:10.1145/77726
Chairmen:
Ahmed Sameh
Univ. of Illinois
,
Henk van der Vorst
Delft Univ. of Technology and CWI, The Netherlands

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1990

Published in SIGARCH Volume 18, Issue 3b

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
424
Total Downloads

Downloads (Last 12 months)78
Downloads (Last 6 weeks)18

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xu DChu CLiu CWang YZhou XZhang LLiang HLi HMohsenin TZhao WChen YMutlu O(2020)Multi-task Scheduling for PIM-based Heterogeneous Computing SystemProceedings of the 2020 on Great Lakes Symposium on VLSI10.1145/3386263.3406946(457-462)Online publication date: 7-Sep-2020
https://dl.acm.org/doi/10.1145/3386263.3406946
Pang DXu DWang YLiang H(2018)MTTF-Aware Reliability Task Scheduling for PIM-Based Heterogeneous Computing System2018 IEEE International Test Conference in Asia (ITC-Asia)10.1109/ITC-Asia.2018.00015(25-30)Online publication date: Aug-2018
https://doi.org/10.1109/ITC-Asia.2018.00015
Friedman AFriedman A(1992)Interprocessor memory contentionMathematics in Industrial Problems10.1007/978-1-4615-7405-7_11(112-121)Online publication date: 1992
https://doi.org/10.1007/978-1-4615-7405-7_11
Peiron MValero MAyguadé ELang T(1995)Vector multiprocessors with arbitrated memory accessACM SIGARCH Computer Architecture News10.1145/225830.22443523:2(243-252)Online publication date: 1-May-1995
https://dl.acm.org/doi/10.1145/225830.224435
Peiron MValero MAyguadé ELang TPatterson D(1995)Vector multiprocessors with arbitrated memory accessProceedings of the 22nd annual international symposium on Computer architecture10.1145/223982.224435(243-252)Online publication date: 1-Jul-1995
https://dl.acm.org/doi/10.1145/223982.224435
Yang QYang T(1995)A Memory Interference Model for Regularly Patterned Multiple Stream Vector AccessesIEEE Transactions on Parallel and Distributed Systems10.1109/71.3823206:5(520-530)Online publication date: 1-May-1995
https://dl.acm.org/doi/10.1109/71.382320
van Gemund AGurd JJalby W(1994)Compiling performance models from parallel programsProceedings of the 8th international conference on Supercomputing10.1145/181181.181546(303-312)Online publication date: 16-Jul-1994
https://dl.acm.org/doi/10.1145/181181.181546
Peiron MValero MAyguadé EGurd JJalby W(1994)Synchronized access to streams in SIMD vector multiprocessorsProceedings of the 8th international conference on Supercomputing10.1145/181181.181204(23-32)Online publication date: 16-Jul-1994
https://dl.acm.org/doi/10.1145/181181.181204
Smith JTaylor WKennedy KPolychronopoulos C(1992)Characterizing memory performance in vector multiprocessorsProceedings of the 6th international conference on Supercomputing10.1145/143369.143379(35-44)Online publication date: 1-Aug-1992
https://dl.acm.org/doi/10.1145/143369.143379
Ganesan RWeiss S(1992)Scalar Memory References in Pipelined MultiprocessorsIEEE Transactions on Software Engineering10.1109/32.12031818:1(78-86)Online publication date: 1-Jan-1992
https://dl.acm.org/doi/10.1109/32.120318
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations