Electrical computers and digital processing systems: processing – Byte-word rearranging – bit-field insertion or extraction,...
Reexamination Certificate
2000-04-07
2004-03-30
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Byte-word rearranging, bit-field insertion or extraction,...
C712S224000, C708S209000
Reexamination Certificate
active
06715066
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of digital computers and more specifically to functional units for processing predetermined types of instructions. The invention particularly provides a circuit or functional unit for use in connection with execution of an instruction for rearranging bits of a data word in accordance with a mask.
BACKGROUND OF THE INVENTION
Computers process data in accordance with instructions. One type of instruction which has been proposed is a so-called “sheep and goats” instruction which accepts as operands a data word and a mask word and rearranges the bits of the data word in accordance with the mask word. In the rearranged data word, the bits of the data word in bit positions which correspond to bits of the mask which are clear, or have the value “zero,” are shifted to the “left” end of the rearranged data word with their order being preserved, and the bits of the data word in bit positions which correspond to bits of the mask which are set, or have the value “one,” are shifted to the right end of the data word with their order being preserved. For example, if an eight bit data word has the value “abcdefgh” (where the letters represent binary integers having the value “one” or “zero”), and the mask word corresponds to “10011011,” in the rearranged data word generated when the “sheep and goats” instruction is executed with these as operands, the bits “b,” “c,” and “f,” all of which are in bit positions for which the mask bits are clear would be shifted to the left, preserving their order “bcf,” and the bits “a,” “d,” “e,” “g,” and “h,” all of which are in bit positions for which the mask bits are set would be shifted to the right, preserving their order “adegh,” with the result being the rearranged data word “bcfadegh.” Essentially, the “sheep and goats” instruction results in a rearrangement of bits of a data word into two groups as defined by bits of a mask word, one group (the “sheep”) corresponding to those bits for which the bits of the mask word are clear, and the other (the “goats”) corresponding to those bits for which the bits of the mask word are set, and in addition preserves order in each group
In a variant of the “sheep and goats” instruction, the bits of the rearranged data word in bit positions for which the bits of the mask are either set or clear (but preferably not both) will be set to a predetermined value. Generally, it has been proposed that, for example, the bits of the rearranged data word in bit positions for which the bits of the mask are clear will be set to zero, but the variant may be used with either the “sheep” or the “goats,” and the predetermined value may be either “one” or “zero.”
A “sheep and goats” instruction can find utility in connection with, for example, performing various bit permutations, for example, using a mask consisting of alternating set and clear bits will result in a so-called “unshuffle” permutation of a data word. In addition, the variant can be useful in connection with using a set of originally discontiguous bits to perform a multi-way dispatch, or jump, by making the bits contiguous and using the result to form an index into a jump table.
SUMMARY OF THE INVENTION
The invention provides a new and improved circuit or functional unit for use in connection with execution of an instruction for rearranging bits of a data word in accordance with a mask. In brief summary, the invention provides a system for rearranging data units of a data word in accordance with a mask word, the mask word having a plurality of mask bits each associated with a data unit, each mask bit having one of a set condition or a clear condition. The system includes a control module and a shifter module. The control module is configured to generate, for each mask bit, values identifying the number of mask bits to the left of the respective mask bit which have one of the set condition or the clear condition and the number of mask bits to the right of the respective mask bit which have the other of the set condition or the clear condition. The shifter module is configured to shift data units of the data word in accordance with the values generated by the control module.
REFERENCES:
patent: 4085447 (1978-04-01), Pertl et al.
patent: 5339447 (1994-08-01), Balmer
patent: 5696922 (1997-12-01), Fromm
patent: 6144986 (2000-11-01), Silver
Tanenbaum, Structured Computer Organization 2nd Edition, 1984, p. 11.*
Scott, “Synchronization and Communication in the T3E Multiprocessor,” Cray Research, Inc., 1996, pp. 26-36.*
Hillis, W. Daniel & Steele, Guy L. Data Parallel Agorithms,Communications of the ACM, Dec. 1986, vol. 29, No. 12, pp.1170-1183.
Chan Eddie
Foley & Hoag LLP
Huisman David J.
LandOfFree
System and method for arranging bits of a data word in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for arranging bits of a data word in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for arranging bits of a data word in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3202550