More Web Proxy on the site http://driver.im/

Article

Free access

Integer multiplication and division on the HP precision architecture

Authors:

Daniel J. Magenheimer,

Dan ZurasAuthors Info & Claims

ASPLOS II: Proceedings of the second international conference on Architectual support for programming languages and operating systems

Pages 90 - 99

https://doi.org/10.1145/36206.36189

Published: 01 October 1987 Publication History

Abstract

In recent years, many architectural design efforts have focused on maximizing performance for frequently executed, simple instructions. Although these efforts have resulted in machines with better average price/performance ratios, certain complex instructions and, thus, certain classes of programs which heavily depend on these instructions may suffer by comparison. Integer multiplication and division are one such set of complex instructions. This paper describes how a small set of primitive instructions combined with careful frequency analysis and clever programming allows the Hewlett-Packard Precision Architecture integer multiplication and division implementation to provide adequate performance at little or no hardware cost.

References

[1]

{Bir85} Birnbaum, J. S., and Worley Jr., W. S., "Beyond RISC: High-Precision Architecture," Hewlett-Packard Journal, Vol. 36, No. 8, August 1985.

[2]

{Boo51} Booth, Andrew D., "A Signed Binary Multiplication Technique", Quart. Journ. Mech. and Applied Math., Vol. IV Pt. 2 (1951), pp. 236--240.

[3]

{Cla82}Clark, D. W., "Measurement and Analysis of Instruction Use in the VAX 11/780," Proc. of the 9th Symposium on Computer Architecture, April 1982, pp. 9--17.

Digital Library

[4]

{Cou86}Coutant, D. S., Hammond, C. L., and Kelley, J. W., "Compilers for the New Generation of Hewlett-Packard Computers," Hewlett-Packard Journal, Vol. 37, No. 1, January 1986.

[5]

{Ele86} "A Simple Design May Pay Off Big for Hewlett-Packard", Electronics, March 3, 1986, pp. 39--47

[6]

{Gib70} Gibson, J. C. "The Gibson Mix," Report TR 00.2043, IBM Systems Development Division, Poughkeepsie, N. Y. 1970.

[7]

{Hen82} Hennessy, J., et al,. "Hardware/Software Tradeoffs for Increased Performance," Proc. Symp. Architectural Support for Programming Languages and Operating Systems (Palo Alto, Ca., March 1--3). ACM, New York, 1982, pp. 2--11.

Digital Library

[8]

{HP86} precision Architecture and Instruction Reference Manual, Hewlett-Packard Co., HP Part Number 09740--90014, November 1986.

[9]

{Huc83} Huck, J. C., Comparative Analysis of Computer Architectures. Ph.D. Th., Stanford University, May 1983.

Digital Library

[10]

{Jou81} Jouppi, N., "MIPS II - Multiplication and Division Features," EE392C Final Reports, Stanford University, June 1981.

[11]

{Knu81} Knuth, D., The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, Addison-Wesley, 1981, pp. 444--446.

Digital Library

[12]

{Luk86} Lukes, J. A., "HP Precision Architecture Performance Analysis," Hewlett-Packard Journal, Vol. 37, No. 8, August 1986.

[13]

{Mah86} Mahon, Michael J., et al., "Hewlett-Packard Precision Architecture: The Processor," Hewlett-Packard Journal, Vol. 37, no. 8, August 1986.

[14]

{Neu79} Neuhauser, Charles J., "Instruction Stream Monitoring of the PDP-11," Stanford University, Dept. of Electrical Engr., Computer Systems Laboratory, Tech. Note No. 156, May 1979

[15]

{Pat82} Patterson, D. A., and Sequin, C. H., "A VLSI RISC," Computer, Vol. 15, No. 9, Sept. 1982, pp. 8--21

Digital Library

[16]

{Pat84} Patterson, D. A.,"RISC Watch" Computer Architecture News, Vol. 12, No. 1, Mar. 1984, pp. 11--19

Digital Library

[17]

{Pat85} Patterson, D. A.,"Reduced Instruction Set Computers" Communications of the ACM, Vol. 12, No. 1, Jan. 1985, pp. 8--21

Digital Library

[18]

{Rad82} Radin, G., "The 801 Minicomputer," Proc. Symp. Architectural Support for Programming Languages and Operating Systems (Palo Alto, Ca., March 1--3). ACM, New York, 1982, pp. 39--47.

Digital Library

[19]

{Shu78} Shustek, L. J., Analysis and Performance of Computer Instruction Sets. Ph.D. Th., Stanford University, May 1977.

Digital Library

[20]

{Swe82} Sweet, R. E. and Sandman, J. G., "Empirical Analysis of the Mesa Instruction Set," Proc. Symp. Architectural Support for Programming Languages and Operating Systems (Palo Alto, Ca., March 1--3). ACM, New York, 1982, pp. 158--166.

Digital Library

[21]

{Was82} Waser, S. and Flynn, M. J., Introduction to Arithmetic for Digital Systems Designers, Holt, Rinehart and Winston, New York, 1982

Digital Library

Cited By

Kuszmaul B(2015)SuperMalloc: a super fast multithreaded malloc for 64-bit machinesACM SIGPLAN Notices10.1145/2887746.275417850:11(41-55)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2887746.2754178
Kuszmaul BHosking ABond M(2015)SuperMalloc: a super fast multithreaded malloc for 64-bit machinesProceedings of the 2015 International Symposium on Memory Management10.1145/2754169.2754178(41-55)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2754169.2754178
DeHon A(2000)The Density Advantage of Configurable ComputingComputer10.1109/2.83932033:4(41-49)Online publication date: 1-Apr-2000
https://dl.acm.org/doi/10.1109/2.839320
Show More Cited By

Index Terms

Integer multiplication and division on the HP precision architecture

Recommendations

Integer multiplication and division on the HP precision architecture

In recent years, many architectural design efforts have focused on maximizing performance for frequently executed, simple instructions. Although these efforts have resulted in machines with better average price/performance ratios, certain complex ...
Integer multiplication and division on the HP precision architecture

In recent years, many architectural design efforts have focused on maximizing performance for frequently executed, simple instructions. Although these efforts have resulted in machines with better average price/performance ratios, certain complex ...
Integer multiplication and division on the HP precision architecture

In recent years, many architectural design efforts have focused on maximizing performance for frequently executed, simple instructions. Although these efforts have resulted in machines with better average price/performance ratios, certain complex ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS II: Proceedings of the second international conference on Architectual support for programming languages and operating systems

October 1987

205 pages

ISBN:0818608056

DOI:10.1145/36206

Editor:
Randy Katz
Univ. of California, Berkeley
,
General Chair:
Martin Freeman
Stanford University and Philips/Signetics

ACM SIGPLAN Notices Volume 22, Issue 10
Oct. 1987
189 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/36205
Editor:
Randy Katz
Univ. of California, Berkeley
Issue’s Table of Contents
ACM SIGOPS Operating Systems Review Volume 21, Issue 4
Oct. 1987
189 pages
ISSN:0163-5980
DOI:10.1145/36204
Editor:
Randy Katz
Univ. of California, Berkeley
Issue’s Table of Contents
ACM SIGARCH Computer Architecture News Volume 15, Issue 5
Oct. 1987
189 pages
ISSN:0163-5964
DOI:10.1145/36177
Editor:
Randy H. Katz
Univ. of California, Berkeley
Issue’s Table of Contents

Copyright © 1987 Copyright is held by the owner/author(s).

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1987

Check for updates

Qualifiers

Article

Conference

ASPLOS II

Sponsor:

SIGARCH

ASPLOS II: Architectual support for programming languages and operating systems

October 5 - 8, 1987

California, Palo Alto, USA

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
947
Total Downloads

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

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kuszmaul B(2015)SuperMalloc: a super fast multithreaded malloc for 64-bit machinesACM SIGPLAN Notices10.1145/2887746.275417850:11(41-55)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2887746.2754178
Kuszmaul BHosking ABond M(2015)SuperMalloc: a super fast multithreaded malloc for 64-bit machinesProceedings of the 2015 International Symposium on Memory Management10.1145/2754169.2754178(41-55)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2754169.2754178
DeHon A(2000)The Density Advantage of Configurable ComputingComputer10.1109/2.83932033:4(41-49)Online publication date: 1-Apr-2000
https://dl.acm.org/doi/10.1109/2.839320
DeHon AWawrzynek J(1999)Reconfigurable computingProceedings of the 36th annual ACM/IEEE Design Automation Conference10.1145/309847.310009(610-615)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1145/309847.310009
Matsuura AYukishita MNagoya A(1997)An efficient hierarchical clustering method for the multiple constant multiplication problemProceedings of ASP-DAC '97: Asia and South Pacific Design Automation Conference10.1109/ASPDAC.1997.600064(83-88)Online publication date: 1997
https://doi.org/10.1109/ASPDAC.1997.600064
Wu Y(1995)Strength reduction of multiplications by integer constantsACM SIGPLAN Notices10.1145/199873.19988030:2(42-48)Online publication date: 1-Feb-1995
https://dl.acm.org/doi/10.1145/199873.199880
Granlund TMontgomery P(1994)Division by invariant integers using multiplicationACM SIGPLAN Notices10.1145/773473.17824929:6(61-72)Online publication date: 1-Jun-1994
https://dl.acm.org/doi/10.1145/773473.178249
Granlund TMontgomery PSarkar VRyder BSoffa M(1994)Division by invariant integers using multiplicationProceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation10.1145/178243.178249(61-72)Online publication date: 1-Aug-1994
https://dl.acm.org/doi/10.1145/178243.178249
Lemire DBartlett CKaser O(2021)Integer division by constants: optimal boundsHeliyon10.1016/j.heliyon.2021.e074427:6(e07442)Online publication date: Jun-2021
https://doi.org/10.1016/j.heliyon.2021.e07442
Carter TRobertson J(1990)Radix-16 Signed-Digit DivisionIEEE Transactions on Computers10.1109/12.6106339:12(1424-1433)Online publication date: 1-Dec-1990
https://dl.acm.org/doi/10.1109/12.61063
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents