Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
2000-11-13
2004-05-04
Kim, Kenneth S. (Department: 2181)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S015000, C712S226000, C712S241000
Reexamination Certificate
active
06732253
ABSTRACT:
TECHNICAL FIELD
This invention relates to loop handling operations over an array of data items in a single instruction multiple datapath (SIMD) processor architecture.
BACKGROUND
Parallel processing is an efficient way of processing an array of data items. A SIMD processor is a parallel processor array architecture wherein multiple datapaths are controlled by a single instruction. Each datapath handles one data item at a given time. In a simple example, in a SIMD processor having four datapaths, the data items in an eight data item array would be processed in each of the four datapaths in two passes of a loop operation. The allocation between datapaths and data items may vary, but in one approach, in a first pass the first data item in the array is processed by a first datapath, a second data item in the array is processed by a second datapath, a third data item is processed by a third datapath, and a fourth data item is processed by a fourth datapath. In a second pass, a fifth data item is processed by the first datapath, a sixth data item is processed by the second datapath, a seventh data item is processed by the third datapath, and an eighth data item is processed by the fourth datapath.
Problems may occur when the number of data items in the array is not an integer multiple of the number of datapaths. For example, modifying the simple example above so that there are four datapaths and an array having seven data items, during the second pass, the fourth datapath does not have an element in the eighth item of the array to process. As a result, the fourth datapath may erroneously write over some other data structure in memory, unless the fourth datapath is disabled during the second pass.
One way of avoiding such erroneous overwriting is to force the size of the array, i.e., the number of data items contained within the array, to be an integer multiple of the number of datapaths. Such an approach assumes that programmers have a priori control of how data items are allocated in the array, which they may not always have.
Typically, each datapath in a SIMD processor has an associated processor enable bit that controls whether a datapath is enabled or disabled. This allows a datapath to be disabled when, e.g., the datapath would otherwise overrun the array.
SUMMARY
In a general aspect, the invention features a method of controlling whether to enable one of a plurality of processor datapaths in a SIMD processor that are operating on data elements in an array, including determining whether to enable the datapath based on information about parameters of the SIMD processor and the array, and a processing state of the datapaths relative to the data items in the array.
In a preferred embodiment, the information includes an allocation between the data items and a memory, a total number of parallel loop passes in a loop processing operation being performed by the datapaths, a size of the array, and a number of datapaths (i.e., how many datapaths there are in the SIMD processor). The processing state is a number of remaining parallel passes of the datapaths in the loop processing operation.
The allocation between the data items and the memory may be unity-stride, contiguous or striped-stride.
In another aspect, the invention features a computer instruction including a loop handling instruction that specifies the enabling of one of a plurality of processor datapaths during processing an array of data items.
In a preferred embodiment, the instruction includes a parallel count field that specifies the number of remaining parallel loop passes to process the array, and a serial count field that specifies the number of serial loop passes to process the array.
In another aspect, the invention features a processor including a register file and an arithmetic logic unit coupled to the register file, and a program control store that stores a loop handling instruction that causes the processor to enable one of a plurality of processor datapaths during processing of an array of data.
Embodiments of various aspects of the invention may have one or more of the following advantages.
Datapaths may be disabled without having prior knowledge of the number of data items in the array.
The method is readily extensible to a variety of memory allocation schemes.
The loop handling instruction saves instruction memory because the many operations needed to determine whether to enable or disable a datapath may be specified with a simple and powerful single instruction that also saves register space.
The loop handling instruction saves a programmer from having to force the number of data items in the array of data items to be an integer multiple of the number of datapaths.
REFERENCES:
patent: 4101960 (1978-07-01), Stokes et al.
patent: 4138720 (1979-02-01), Chu et al.
patent: 4181942 (1980-01-01), Forster et al.
patent: 4410939 (1983-10-01), Kawakami
patent: 4434461 (1984-02-01), Puhl
patent: 4435758 (1984-03-01), Lorie et al.
patent: 4592013 (1986-05-01), Prame
patent: 4604695 (1986-08-01), Widen et al.
patent: 4679140 (1987-07-01), Gotou et al.
patent: 4773038 (1988-09-01), Hillis et al.
patent: 4992933 (1991-02-01), Taylor
patent: 5021993 (1991-06-01), Matoba et al.
patent: 5038282 (1991-08-01), Gilbert et al.
patent: 5045995 (1991-09-01), Levinthal et al.
patent: 5111389 (1992-05-01), McAuliffe et al.
patent: 5121498 (1992-06-01), Gilbert et al.
patent: 5136697 (1992-08-01), Johnson
patent: 5224214 (1993-06-01), Rosich
patent: 5230079 (1993-07-01), Grondalski
patent: 5276895 (1994-01-01), Grondalski
patent: 5361367 (1994-11-01), Fijany et al.
patent: 5430854 (1995-07-01), Sprague et al.
patent: 5479624 (1995-12-01), Lee
patent: 5497478 (1996-03-01), Murata
patent: 5524223 (1996-06-01), Lazaravich et al.
patent: 5542074 (1996-07-01), Kim et al.
patent: 5551039 (1996-08-01), Weinberg et al.
patent: 5555386 (1996-09-01), Nomura
patent: 5555428 (1996-09-01), Radigan et al.
patent: 5590283 (1996-12-01), Hillis et al.
patent: 5590356 (1996-12-01), Gilbert
patent: 5604913 (1997-02-01), Koyanagi et al.
patent: 5608886 (1997-03-01), Blomgren et al.
patent: 5638533 (1997-06-01), Law
patent: 5659722 (1997-08-01), Blaner et al.
patent: 5659778 (1997-08-01), Gingold et al.
patent: 5666519 (1997-09-01), Hayden
patent: 5684973 (1997-11-01), Sullivan et al.
patent: 5696958 (1997-12-01), Mowry et al.
patent: 5737572 (1998-04-01), Nunziata
patent: 5752068 (1998-05-01), Gilbert
patent: 5758112 (1998-05-01), Yeager et al.
patent: 5758176 (1998-05-01), Agarwal et al.
patent: 5778241 (1998-07-01), Bindloss et al.
patent: 5805915 (1998-09-01), Wilkerson et al.
patent: 5822606 (1998-10-01), Morton
patent: 5848290 (1998-12-01), Yoshida et al.
patent: 5870581 (1999-02-01), Redford
patent: 5872987 (1999-02-01), Wade et al.
patent: 5924117 (1999-07-01), Luick
patent: 5933650 (1999-08-01), van Hook et al.
patent: 5946222 (1999-08-01), Redford
patent: 5991857 (1999-11-01), Koetje et al.
patent: 6049330 (2000-04-01), Redford
patent: 6052703 (2000-04-01), Redford
patent: 6067609 (2000-05-01), Mecker et al.
patent: 6076158 (2000-06-01), Sites et al.
patent: 6121905 (2000-09-01), Redford
patent: 6130631 (2000-10-01), Redford
patent: 6175892 (2001-01-01), Sazzard et al.
patent: 6211864 (2001-04-01), Redford
patent: 6216223 (2001-04-01), Revilla et al.
patent: 6282623 (2001-08-01), Halahmi et al.
patent: 6282628 (2001-08-01), Dubey et al.
patent: 6292879 (2001-09-01), Fong
patent: 6381668 (2002-04-01), Lunteren
patent: 6404439 (2002-06-01), Coulombe et al.
patent: 6452864 (2002-09-01), Condemi et al.
patent: 6473339 (2002-10-01), De Ambroggi et al.
patent: 6487651 (2002-11-01), Jackson et al.
patent: 0 314 277 (1989-05-01), None
patent: 0 552 816 (1993-07-01), None
patent: 0 679 991 (1995-11-01), None
patent: 0 945 783 (1999-09-01), None
patent: 0 681 236 (2000-11-01), None
patent: 2 201 015 (1988-08-01), None
patent: 2201015 (1988-08-01), None
patent: 10/289305 (1998-10-01), None
patent: 2002-7359 (2002-01-01), None
patent: WO 87/00318 (1987-01-01), None
patent: WO 91/19269 (1991-12-01), None
patent: WO 93/04438 (1993-03-01), None
patent: WO 9
ChipWrights Design, Inc.
Fish & Richardson P.C.
Kim Kenneth S.
LandOfFree
Loop handling for single instruction multiple datapath... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Loop handling for single instruction multiple datapath..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Loop handling for single instruction multiple datapath... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222941