[go: up one dir, main page]

WO1997007451A3 - Method and system for implementing data manipulation operations - Google Patents

Method and system for implementing data manipulation operations Download PDF

Info

Publication number
WO1997007451A3
WO1997007451A3 PCT/US1996/013195 US9613195W WO9707451A3 WO 1997007451 A3 WO1997007451 A3 WO 1997007451A3 US 9613195 W US9613195 W US 9613195W WO 9707451 A3 WO9707451 A3 WO 9707451A3
Authority
WO
WIPO (PCT)
Prior art keywords
elements
array
permutations
copying
data
Prior art date
Application number
PCT/US1996/013195
Other languages
French (fr)
Other versions
WO1997007451A2 (en
Inventor
Thomas J Karzes
Craig C Hansen
Henry Massalin
Original Assignee
Microunity Systems Eng
Thomas J Karzes
Craig C Hansen
Henry Massalin
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 Microunity Systems Eng, Thomas J Karzes, Craig C Hansen, Henry Massalin filed Critical Microunity Systems Eng
Priority to AU68467/96A priority Critical patent/AU6846796A/en
Publication of WO1997007451A2 publication Critical patent/WO1997007451A2/en
Publication of WO1997007451A3 publication Critical patent/WO1997007451A3/en

Links

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/76Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
    • G06F7/762Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data having at least two separately controlled rearrangement levels, e.g. multistage interconnection networks
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/76Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00Arrangements for program control, e.g. control units
    • G06F9/06Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003Arrangements for executing specific machine instructions
    • G06F9/30007Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30018Bit or string instructions
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00Arrangements for program control, e.g. control units
    • G06F9/06Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003Arrangements for executing specific machine instructions
    • G06F9/30007Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30025Format conversion instructions, e.g. Floating-Point to Integer, decimal conversion
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00Arrangements for program control, e.g. control units
    • G06F9/06Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003Arrangements for executing specific machine instructions
    • G06F9/30007Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30032Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00Arrangements for program control, e.g. control units
    • G06F9/06Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003Arrangements for executing specific machine instructions
    • G06F9/30007Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30036Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
    • G06F9/30038Instructions to perform operations on packed data, e.g. vector, tile or matrix operations using a mask

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Complex Calculations (AREA)

Abstract

A method and system for performing arbitrary permutations of sequences of elements. In the general case, the method of the present invention processes the elements to be permuted as a multi-dimensional array, where each element in the array corresponds to one of the elments to be permuted. The permutation is achieved by performing a sequence of sets of permutations, where each set of permutations in the sequence independently permutes the elements within each one-dimensional slice through the array, along some particular dimension of the array. The total number of sets of permutations, or stages, is one less than twice the number of dimensions in the array. An extension to the general method allows some extensions of permutations which involve the copying of individual elements. A system based on the extended general method implements a large class of operations which involve copying and/or permuting elements, where the sequence of elements is a word of data and the elements are bits of data. An efficient control structure for the system permits control signals to be shared across slices of the array. A version of the system based on a two-dimensional array includes three multiplex stages, where the first stage multiplexes along the rows, the second stage multiplexes along the columns, and the third stage multiplexes across the rows once again. Several classes of computer instructions which generally involve the copying and/or permuting of data are also described.
PCT/US1996/013195 1995-08-16 1996-08-14 Method and system for implementing data manipulation operations WO1997007451A2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU68467/96A AU6846796A (en) 1995-08-16 1996-08-14 Method and system for implementing data manipulation operations

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US51639895A 1995-08-16 1995-08-16
US08/516,398 1995-08-16

Publications (2)

Publication Number Publication Date
WO1997007451A2 WO1997007451A2 (en) 1997-02-27
WO1997007451A3 true WO1997007451A3 (en) 1997-04-10

Family

ID=24055396

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1996/013195 WO1997007451A2 (en) 1995-08-16 1996-08-14 Method and system for implementing data manipulation operations

Country Status (2)

Country Link
AU (1) AU6846796A (en)
WO (1) WO1997007451A2 (en)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6871303B2 (en) 1998-12-04 2005-03-22 Qualcomm Incorporated Random-access multi-directional CDMA2000 turbo code interleaver
US6304991B1 (en) * 1998-12-04 2001-10-16 Qualcomm Incorporated Turbo code interleaver using linear congruential sequence
US6446198B1 (en) 1999-09-30 2002-09-03 Apple Computer, Inc. Vectorized table lookup
WO2023086271A1 (en) * 2021-11-15 2023-05-19 Google Llc Sparse simd cross-lane processing unit
US11966745B2 (en) 2021-11-15 2024-04-23 Google Llc Sparse SIMD cross-lane processing unit
US12353887B2 (en) 2021-11-15 2025-07-08 Google Llc Programmable accelerator for data-dependent, irregular operations
US11972263B2 (en) 2021-11-22 2024-04-30 Google Llc Cooperative instruction prefetch on multicore system
US11977499B2 (en) 2022-03-22 2024-05-07 Google Llc Streaming transfers and ordering model

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3812467A (en) * 1972-09-25 1974-05-21 Goodyear Aerospace Corp Permutation network
WO1990001740A1 (en) * 1988-08-01 1990-02-22 Board Of Regents, The University Of Texas System Dynamic address mapping for conflict-free vector access
EP0376769A2 (en) * 1988-11-25 1990-07-04 France Telecom Apparatus for line-column matrix transposition using shift registers and permutation operators
US5159690A (en) * 1988-09-30 1992-10-27 Massachusetts Institute Of Technology Multidimensional cellular data array processing system which separately permutes stored data elements and applies transformation rules to permuted elements

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3812467A (en) * 1972-09-25 1974-05-21 Goodyear Aerospace Corp Permutation network
WO1990001740A1 (en) * 1988-08-01 1990-02-22 Board Of Regents, The University Of Texas System Dynamic address mapping for conflict-free vector access
US5159690A (en) * 1988-09-30 1992-10-27 Massachusetts Institute Of Technology Multidimensional cellular data array processing system which separately permutes stored data elements and applies transformation rules to permuted elements
EP0376769A2 (en) * 1988-11-25 1990-07-04 France Telecom Apparatus for line-column matrix transposition using shift registers and permutation operators

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
ANTZOULATOS D G ET AL: "HYPERMATRIX ALGEBRA: THEORY", CVGIP IMAGE UNDERSTANDING, vol. 57, no. 1, 1 January 1993 (1993-01-01), pages 24 - 41, XP000382765 *
FRASER: "Array Permutation by Index-Digit Permutation", JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, vol. 23, no. 2, April 1976 (1976-04-01), pages 298 - 309, XP002025764 *
HANNA C A ET AL: "BIT MANIPULATOR", IBM TECHNICAL DISCLOSURE BULLETIN, vol. 17, no. 6, 1 November 1974 (1974-11-01), pages 1575/1576, XP002011206 *

Also Published As

Publication number Publication date
AU6846796A (en) 1997-03-12
WO1997007451A2 (en) 1997-02-27

Similar Documents

Publication Publication Date Title
DE60035171T2 (en) Methods and circuits for quickly finding the minimum / maximum value in a set of numbers
Seiden et al. On orthogonal arrays
DE60004407T2 (en) INTERLAYER AND NESTLING METHOD OF A DATA INPUT SEQUENCE USING A CODED RECORDING OF SYMBOLS AND ADDITIONAL INFORMATION
EP1009124A3 (en) Wireless transmission method for antenna arrays using unitary space-time signals
Dillon et al. Simon Newcomb’s problem
WO1997007451A3 (en) Method and system for implementing data manipulation operations
WO2002013449A3 (en) Apparatus and method for providing turbo code interleaving in a communications system
CA2076610A1 (en) Generating system of random-number sequences for a parallel computer system
CA2342519A1 (en) Display system facilitating paint color selection and coordination
EP1034686A4 (en) A low latency shared memory switch architecture
WO1998034294A3 (en) Multi-dimensional beamforming device
CA2287608A1 (en) File management method using transposed file
CA2309906A1 (en) System and method for data planarization
Golomb Permutations by cutting and shuffling
CA2366581A1 (en) Intra-row permutation for turbocode
Patterson Rates of convergence for double sequences
EP0921477A3 (en) Orthogonal transform apparatus
Mayoh A graph technique for inverting certain matrices
Dontcheva et al. Some extremal self-dual codes with an automorphism of order 7
WO2003049423A3 (en) System and method for scaling an image
IL159704A (en) Dct matrix decomposing method and dct device
Federer et al. Construction of lattice square designs
Preece A second domain of balanced 6× 6 designs for nine equally-replicated treatments
EP0404398A3 (en) Data processing system
Nigam On some balanced row-and-column designs

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AL AM AT AU AZ BB BG BR BY CA CH CN CU CZ DE DK EE ES FI GB GE HU IL IS JP KE KG KP KR KZ LK LR LS LT LU LV MD MG MK MN MW MX NO NZ PL PT RO RU SD SE SG SI SK TJ TM TR TT UA UG US UZ VN AM AZ BY KG KZ MD RU TJ TM

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): KE LS MW SD SZ UG AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE BF BJ CF CG CI CM

AK Designated states

Kind code of ref document: A3

Designated state(s): AL AM AT AU AZ BB BG BR BY CA CH CN CU CZ DE DK EE ES FI GB GE HU IL IS JP KE KG KP KR KZ LK LR LS LT LU LV MD MG MK MN MW MX NO NZ PL PT RO RU SD SE SG SI SK TJ TM TR TT UA UG US UZ VN AM AZ BY KG KZ MD RU TJ TM

AL Designated countries for regional patents

Kind code of ref document: A3

Designated state(s): KE LS MW SD SZ UG AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE BF BJ CF CG CI CM

121 Ep: the epo has been informed by wipo that ep was designated in this application
DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

122 Ep: pct application non-entry in european phase
NENP Non-entry into the national phase

Ref country code: CA