[go: up one dir, main page]

WO2009037684A3 - Sparse matrix by vector multiplication - Google Patents

Sparse matrix by vector multiplication Download PDF

Info

Publication number
WO2009037684A3
WO2009037684A3 PCT/IE2008/000089 IE2008000089W WO2009037684A3 WO 2009037684 A3 WO2009037684 A3 WO 2009037684A3 IE 2008000089 W IE2008000089 W IE 2008000089W WO 2009037684 A3 WO2009037684 A3 WO 2009037684A3
Authority
WO
WIPO (PCT)
Prior art keywords
matrix
vector multiplication
vector
sparse matrix
allows
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/IE2008/000089
Other languages
French (fr)
Other versions
WO2009037684A2 (en
Inventor
Thomas Dermot Geraghty
David Gregg
Bartley Mcelroy
Fergal Connor
Ciarán McELROY
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
College of the Holy and Undivided Trinity of Queen Elizabeth near Dublin
Original Assignee
College of the Holy and Undivided Trinity of Queen Elizabeth near Dublin
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by College of the Holy and Undivided Trinity of Queen Elizabeth near Dublin filed Critical College of the Holy and Undivided Trinity of Queen Elizabeth near Dublin
Publication of WO2009037684A2 publication Critical patent/WO2009037684A2/en
Anticipated expiration legal-status Critical
Publication of WO2009037684A3 publication Critical patent/WO2009037684A3/en
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Computational Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • Algebra (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Complex Calculations (AREA)

Abstract

The invention involves pre-processing the matrix according to an encoding scheme whereby the non-zero data (in any numerical format), blocking information, the row an column offset indices within a block are represented by state machine control words which are combined in a single data stream. Thus, a single vector may be used to store all of the matrix information required to compute a sparse matrix by vector multiplication. Therefore, the system can be used effectively with a single memory channel. Also, it can be used in parallel with multiple independent memory channels. This method of matrix-by-vector multiplication achieves allows very high FPU utilization to be achieved for low bandwidth matrices such as those from finite element calculations. Also, it allows local memory buffers to be simple, and so there is no need for a complex cache architecture.
PCT/IE2008/000089 2007-09-19 2008-09-19 Sparse matrix by vector multiplication Ceased WO2009037684A2 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US96017607P 2007-09-19 2007-09-19
US60/960,176 2007-09-19

Publications (2)

Publication Number Publication Date
WO2009037684A2 WO2009037684A2 (en) 2009-03-26
WO2009037684A3 true WO2009037684A3 (en) 2010-05-06

Family

ID=40468549

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/IE2008/000089 Ceased WO2009037684A2 (en) 2007-09-19 2008-09-19 Sparse matrix by vector multiplication

Country Status (1)

Country Link
WO (1) WO2009037684A2 (en)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8676874B2 (en) 2010-12-06 2014-03-18 International Business Machines Corporation Data structure for tiling and packetizing a sparse matrix
US8762655B2 (en) * 2010-12-06 2014-06-24 International Business Machines Corporation Optimizing output vector data generation using a formatted matrix data structure
US9367519B2 (en) 2013-08-30 2016-06-14 Microsoft Technology Licensing, Llc Sparse matrix data structure
CN117933314A (en) * 2017-04-21 2024-04-26 上海寒武纪信息科技有限公司 Processing device, processing method, chip and electronic device
US10055383B1 (en) 2017-04-28 2018-08-21 Hewlett Packard Enterprise Development Lp Matrix circuits
CN112257372B (en) * 2020-12-21 2021-03-30 北京智芯仿真科技有限公司 Method and system for extracting impedance network model of integrated circuit
KR20220090152A (en) * 2020-12-22 2022-06-29 에스케이하이닉스 주식회사 Storage device and operating method thereof
CN112991142B (en) * 2021-03-31 2023-06-16 腾讯科技（深圳）有限公司 Matrix operation method, device, equipment and storage medium for image data

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2006120664A2 (en) * 2005-05-13 2006-11-16 Provost Fellows And Scholars Of The College Of The Holy And Undivided Trinity Of Queen Elizabeth Near Dublin A data processing system and method

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2006120664A2 (en) * 2005-05-13 2006-11-16 Provost Fellows And Scholars Of The College Of The Holy And Undivided Trinity Of Queen Elizabeth Near Dublin A data processing system and method

Non-Patent Citations (9)

* Cited by examiner, † Cited by third party
Title
DELORIMIER M ET AL: "Floating-point sparse matrix-vector multiply for FPGAs", PROCEEDINGS OF THE 2005 ACM/SIGDA 13TH INTERNATIONAL SYMPOSIUM ON FIELD-PROGRAMMABLE GATE ARRAYS (FPGA'05), 20-22 FEBRUARY 2005, MONTEREY, CALIFORNIA, USA, 2005, XP002571772 *
EUN-JIN IM ET AL: "SPARSITY: Optimization framework for sparse matrix kernels", INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS, vol. 18, no. 1, 2004, pages 135 - 158, XP002571764 *
GREGG D ET AL: "FPGA based sparse matrix vector multiplication using commodity DRAM memory", PROCEEDINGS OF INTERNATIONAL CONFERENCE ON FIELD PROGRAMMABLE LOGIC AND APPLICATIONS 2007 (FPL 2007), 27-29 AUGUST 2007, AMSTERDAM, NETHERLANDS, 27 August 2007 (2007-08-27), pages 786 - 791, XP031159191, ISBN: 978-1-4244-1059-0 *
LEE B C ET AL: "Performance models for evaluation and automatic tuning of symmetric sparse matrix-vector multiply", INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING 2004 (ICPP 2004), 15-18 AUGUST 2004, MONTREAL, QC, CANADA, 15 August 2004 (2004-08-15), pages 169 - 176, XP010718617, ISBN: 978-0-7695-2197-8 *
MCGETTRICK S ET AL: "An FPGA architecture for the Pagerank eigenvector problem", PROCEEDINGS OF INTERNATIONAL CONFERENCE ON FIELD PROGRAMMABLE LOGIC AND APPLICATIONS 2008 (FPL 2008), 8-10 SEPTEMBER 2008, HEIDELBERG, GERMANY, 8 September 2008 (2008-09-08), pages 523 - 526, XP031324414, ISBN: 978-1-4244-1960-9 *
MOLONEY D ET AL: "Streaming sparse matrix compression/decompression", PROCEEDINGS OF THE FIRST INTERNATIONAL CONFERENCE ON HIGH-PERFORMANCE EMBEDDED ARCHITECTURES AND COMPILERS (HIPEAC 2005), 17-18 NOVEMBER 2005, BARCELONA, SPAIN, LECTURE NOTES IN COMPUTER SCIENCE, vol. 3793, November 2005 (2005-11-01), pages 116 - 129, XP019024259, ISBN: 978-3-540-30317-6 *
SMAILBEGOVIC F ET AL: "Sparse matrix storage format", PROCEEDINGS OF THE 16TH ANNUAL WORKSHOP ON CIRCUITS, SYSTEMS AND SIGNAL PROCESSING, NOVEMBER 2005, VELDHOVEN, NETHERLANDS, November 2005 (2005-11-01), pages 445 - 448, XP002571766 *
SUN J ET AL: "Mapping sparse matrix-vector multiplication on FPGAs", PROCEEDINGS OF THE THIRD ANNUAL RECONFIGURABLE SYSTEMS SUMMER INSTITUTE (RSSI'07), 17-20 JULY 2007, URBANA, ILLINOIS, USA, 17 July 2007 (2007-07-17), XP002571763, Retrieved from the Internet <URL:http://rssi.ncsa.illinois.edu/proceedings/papers/rssi07_12_paper.pdf> [retrieved on 20100305] *
ZHUO L ET AL: "Sparse matrix-vector multplication on FPGAs", PROCEEDINGS OF THE 2005 ACM/SIGDA 13TH INTERNATIONAL SYMPOSIUM ON FIELD-PROGRAMMABLE GATE ARRAYS (FPGA'05), 20-22 FEBRUARY 2005, MONTEREY, CALIFORNIA, USA, 2005, XP002571765 *

Also Published As

Publication number Publication date
WO2009037684A2 (en) 2009-03-26

Similar Documents

Publication Publication Date Title
WO2009037684A3 (en) Sparse matrix by vector multiplication
US8150031B2 (en) Method and apparatus to perform redundant array of independent disks (RAID) operations
CN105431905B (en) Storage unit with internal read-modify-write operations
WO2008018925A3 (en) Control word key store for multiple data streams
WO2009020969A3 (en) Ecc functional block placement in a multi-channel mass storage device
US20100211747A1 (en) Processor with reconfigurable architecture
WO2009035505A3 (en) Storing operational information in an array of memory cells
CN105874774B (en) Count table holding device for holding count table during processing of frame and related holding method
US10863138B2 (en) Single pass parallel encryption method and apparatus
WO2008156335A3 (en) Method of performing interleaving and data transmission apparatus
JP2008005374A (en) Multi-stream compatible multiplexer and demultiplexer system
WO2008121664A3 (en) Video processing architecture
EP2651070B1 (en) Code processing device, code processing method, and program
WO2008024274A3 (en) Dual mode aes implementation to support single and multiple aes operations
US10637780B2 (en) Multiple datastreams processing by fragment-based timeslicing
EP2183663B1 (en) Mass storage system with improved usage of buffer capacity
WO2009066384A1 (en) Data transmission apparatus
WO2006071725A3 (en) Memory system with in-stream data encryption/decryption
JP2016520239A5 (en)
WO2006069273A3 (en) Memory system with in stream data encryption/decryption and error correction
US8887031B2 (en) Error correcting method, error correcting apparatus, sending device, receiving device, and error correcting program
WO2010002106A3 (en) Circuit for driving lcd device and driving method thereof
KR100248395B1 (en) Channel encoder design method for digital communication
US5910783A (en) Pseudo barrel shifting for entropy encoding
US20090310657A1 (en) Method for Low Power Communication Encoding

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 08807996

Country of ref document: EP

Kind code of ref document: A2

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 08807996

Country of ref document: EP

Kind code of ref document: A2