Method, apparatus and system forming the sum of data in plural equal sections of a single data word

• US 5,727,225 A
• Filed: 06/07/1995
• Issued: 03/10/1998
• Est. Priority Date: 11/30/1993
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Guttag, Karl M., Read, Christopher J.
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): DAVIS JR, WALTER D
• Application Number:
  US08/473,380
• Time in Patent Office: 1,007 Days
• Field of Search: 395/800, 395/421.1, 395/375, 364/736, 364/DIG. 1, 364/749
• US Class Current: 712/224
• CPC Class Codes: G06F 17/153 Multidimensional correlation or convolution

Abstract

This invention is a technique for summing plural sections of a single data word. The technique uses a repeated process forming larger and larger partial sums. Initially the single data word is rotated one section. The original single data word and the rotated single data word are masked with a mask having "1'"'"'s" and "0'"'"'s" in alternate sections. The mask blocks alternate sections so that adjacent sections of the original data word may be summed on a whole data word basis without any overflow disrupting the partial products. The two masked data words are then summed. This sum results in half as many partial sums as before. Each of these larger partial sums now occupies two original sections of the data word. The process can be repeated for these large partial sums. In the preferred embodiment this technique is used with an arithmetic logic unit (230) capable of forming mixed arithmetic and Boolean combinations of three inputs having a barrel rotator (235) driving one input. The arithmetic logic unit (230) receives the single data word at a first input (241) and the rotated single data word at a second input (241). The mask supplies the third input (243). The arithmetic logic unit (230) then forms the combination (A&C)+(B&C), which is field addition of A and B as masked by C. With proper selection of the mask and the rotate amount, the three input arithmetic logic unit (230) forms the shift, mask and addition in a single cycle.

Claims

1. A method for forming a sum of data in 2^N equal sections of a single data word comprising the steps of for each M from 1 to N:

forming an Mth mask having bits of a first digital state filling M odd alternate sections and bits of a second digital state filling M even alternate sections, said second digital state being opposite to said first digital state;

masking a prior sum data word by a first mask thereby forming a prior sum masked data word, the prior sum data word for M=1 being the single data word;

rotating the prior sum data word by M sections;

masking the rotated prior sum data word by the Mth mask thereby forming a rotated prior sum masked data word;

summing the prior sum masked data word and the rotated prior sum masked data word thereby forming a sum data word, a last sum data word being the sum of data in 2N equal sections of the single data word; and

said steps of masking the prior sum data word, rotating the prior sum data word, masking the rotated prior sum data word and summing the prior sum masked data word and the rotated prior sum masked data word occur during a single data processor pipeline stage for each M in a three input arithmetic logic unit, said three input arithmetic logic unit having a first input receiving the prior sum data word, a second input receiving the rotated prior sum data word, a third input receiving the Mth mask and an output generating the summed prior sum masked data word and rotated prior sum masked data word.

2. The method of claim 1, wherein:

said step of masking the prior sum data word consists of forming a logical AND of the Mth mask and the prior sum data word; and

said step of masking the rotated prior sum data word consists of forming the logical AND of the Mth mask and the rotated prior sum data word.

3. The method of claim 1, wherein:

said step of rotating the prior sum data word occurs in a barrel rotator, said barrel rotator having a data input, a rotate control input receiving a rotate control signal, and a data output.

4. The method of claim 1, wherein:

each of said Mth masks has said first digital state equal to "1" and said second digital state equal to "0".

5. A method for forming a sum of data in plural equal sections of a single data word comprising the steps of repeatedly:

forming a mask having bits of a first digital state filling odd alternate portions and bits of a second digital state filling even alternate portions, said second digital state being opposite to said first digital state, said portion initially having a size equal to a section;

masking a prior sum data word by the mask thereby forming a masked prior sum data word, the single data word being a first prior sum data word;

rotating the prior sum data word by one portion;

masking the rotated prior sum data word by the mask thereby forming a masked rotated prior sum data word;

summing the masked prior sum data word and the masked rotated prior sum data word, thereby forming a sum data word;

said steps of masking the prior sum data word, rotating the prior sum data word, masking the rotated prior sum data word and summing the prior sum masked data word and the rotated prior sum masked data word occur during a single data processor pipeline stage for each repetition in a three input arithmetic logic unit, said three input arithmetic logic unit having a first input receiving the prior sum data word, a second input receiving the rotated prior sum data word, a third input receiving the mask and an output generating the sum of the prior sum masked data word and the rotated prior sum masked data word; and

doubling said size of each of said portions for a next repetition, until all sections are summed.

6. The method of claim 5, wherein:

said step of masking the prior sum data word consists of forming the logical AND of the mask and the prior sum data word; and

said step of masking the rotated prior sum data word consists of forming the logical AND of the mask and the rotated prior sum data word.

7. The method of claim 5, wherein:

said step of rotating the prior sum data word occurs in a barrel rotator, said barrel rotator having a data input, a rotate control input receiving a rotate control signal, and a data output.

8. The method of claim 5, wherein:

each of said masks has said first digital state equal to "1" and said second digital state equal to "0".

9. A method for forming a sum of data in four equal sections of a single data word comprising the steps of:

forming a first mask having "1'"'"'s" filling a first and a third section and "0'"'"'s" filling a second and a fourth section;

masking the single data word by the first mask thereby forming a first masked data word;

rotating the single data word by one section;

masking the rotated single data word by the first mask thereby forming a second masked data word;

summing the first masked data word and the second masked data word thereby forming a first sum data word;

said steps of masking the single data word, rotating the single data word, masking the rotated single data word and summing the first masked data word and the second masked data word occurs during a single data processor pipeline stage in a three input arithmetic logic unit, said three input arithmetic logic unit having a first input receiving the single data word, a second input receiving a the rotated single data word, a third input receiving the first mask, and an output generating the sum;

forming a second mask having "1'"'"'s" filling the first and second sections and "0'"'"'s" filling the third and fourth sections;

masking the first sum data word by the second mask thereby forming a third masked data word;

rotating the first sum data word by two sections;

masking the rotated first sum data word by the second mask thereby forming a fourth masked data word;

summing the third masked data word and the fourth masked data word thereby forming a resultant data word; and

said steps of masking the first sum data word, rotating the first sum data word, masking the rotated first sum data word and summing the third masked data word and the fourth masked data word occur during a single data processor pipeline stage in a three input arithmetic logic unit, said three input arithmetic logic unit having a first input receiving the first sum data word, a second input receiving the rotated first sum data word, a third input receiving the second mask, and an output generating the sum.

10. The method of claim 9, wherein:

each of said steps of rotating the single data word and rotating the first sum data word occurs in a barrel rotator, said barrel rotator having a data input, a rotate control input receiving a rotate control signal, and a data output.

11. A data processing apparatus forming a sum of data in plural equal sections of a single data word comprising:

a three input arithmetic logic unit having first, second and third signal inputs, a function input and an output;

a barrel rotator having a data input, a rotate control input receiving a rotate control signal, and a data output connected to said second signal input of the arithmetic logic unit, said barrel rotator left rotating data supplied to said data input an amount corresponding to said rotate control signal and supplying left rotated data to said second signal input of said arithmetic logic unit;

a data register file including

a plurality of data registers for storing data, said single data word initially stored in a first predetermined data register of said plurality of data registers,

a first output bus connected to said first signal input of said arithmetic logic unit for recalling from a first instruction specified data register selected from among all of said plurality of data registers the data stored therein,

a second output bus connected to said data input of said barrel rotator for recalling from a second instruction specified data register selected from among all of said plurality of data registers the data stored therein,

a first input bus connected to said output of said arithmetic logic unit for storing in a third instruction specified data register selected from among all of said plurality of data registers said output of said arithmetic logic unit;

an instruction decoder responsive to a stream of instructions and connected to said plurality of data registers, said arithmetic logic unit and said barrel rotator, said instruction decoder responsive to a first instruction in which said first, second and third instruction specified data registers are identical and equal to said first predetermined data register storing said single data word to

supply data stored in said first predetermined data register to said first signal input of said arithmetic logic unit and to said data input of said barrel rotator,

supply a corresponding mask to said third signal input of said arithmetic logic unit,

supply a rotate amount to said rotate control input of said barrel rotator,

control said arithmetic logic unit to perform addition of data received at said first and second signal inputs as masked by said corresponding mask received at said third signal input, and

store an output of said arithmetic logic unit in said first instruction specified data register;

whereby repeated receipt of said first instruction together with corresponding masks and rotate amounts sums larger and larger number of sections of the single data word.

12. The data processing apparatus of claim 11, wherein:

said mask having "1'"'"'s" filling odd alternate M sections and "0'"'"'s" filling even alternate M sections, where M is the number of repetitions of said first instruction; and

said rotate amount is equal to 2^M sections.

13. The data processing apparatus of claim 11, wherein:

said data register file further includes

a second input bus connected to said data output of said barrel rotator for storing in a fifth instruction specified data register selected from among all of said plurality of data registers said data output of said barrel rotator.

14. A data processing apparatus forming a sum of data in four equal sections of a single data word comprising:

a three input arithmetic logic unit having first, second and third signal inputs, a function input and an output;

a barrel rotator having a data input, a rotate control input receiving a rotate control signal, and a data output connected to said second signal input of the arithmetic logic unit, said barrel rotator left rotating data supplied to said data input an amount corresponding to said rotate control signal and supplying left rotated data to said second signal input of said arithmetic logic unit;

a data register file including

a plurality of data registers for storing data, said single data word initially stored in a first predetermined data register of said plurality of data registers,

a first output bus connected to said first signal input of said arithmetic logic unit for recalling from a first instruction specified data register selected from among all of said plurality of data registers the data stored therein,

a second output bus connected to said data input of said barrel rotator for recalling from a second instruction specified data register selected from among all of said plurality of data registers the data stored therein,

a third output bus for recalling from a third instruction specified data register selected from among all of said plurality of data registers the data stored therein,

a first input bus connected to said output of said arithmetic logic unit for storing in a fourth instruction specified data register selected from among all of said plurality of data registers said output of said arithmetic logic unit;

an instruction decoder responsive to a stream of instructions and connected to said plurality of data registers, said arithmetic logic unit and said barrel rotator, said instruction decoder responsive to a first instruction in which said first, second and fourth instruction specified data registers are identical and correspond to said first predetermined data register to

supply data stored in said first predetermined data register to said first signal input of said arithmetic logic unit and to said data input of said barrel rotator,

supply a first mask having "1'"'"'s" filling a first and a third section and "0'"'"'s" filling a second and a fourth section to said third signal input of said arithmetic logic unit,

supply a first rotate amount corresponding to one section of said single data word to said rotate control input of said barrel rotator,

control said arithmetic logic unit to perform addition of data received at said first and second signal inputs as masked by said first mask received at said third signal input, and

store an output of said arithmetic logic unit in said first predetermined data register,

said instruction decoder responsive to a second instruction in which said first, second and fourth instruction specified data registers are identical and correspond to said first predetermined data register to

supply from said first predetermined data register to said first signal input of said arithmetic logic unit and to said data input of said barrel rotator,

supply a second mask having "1'"'"'s" filling said first and second sections and "0'"'"'s" filling said third and fourth sections to said third signal input of said arithmetic logic unit,

supply a rotate amount corresponding to two sections of said single data word to said rotate control input of said barrel rotator,

control said arithmetic logic unit to perform addition of data received at said first and second signal inputs as masked by said second mask received at said third signal input, and

store said output of said arithmetic logic unit in said first predetermined data register.

15. The data processing apparatus claimed in claim 14, wherein:

said first mask is stored in a second predetermined data register of said plurality of data registers;

said third instruction specified data register of said first instruction corresponds to said second predetermined data register; and

said instruction decoder supplies data from said second predetermined data register via said third output bus of said data register file to said third signal input of said arithmetic logic unit in response to said first instruction thereby supplying said first mask to said third signal input of said arithmetic logic unit.

16. The data processing apparatus claimed in claim 14, wherein:

said first rotate amount is stored in a predetermined data field in a third predetermined data register; and

said instruction decoder supplies data from said predetermined data field of said third predetermined data register to said rotate control input of said barrel rotator in response to said first instruction.

17. The data processing apparatus claimed in claim 14, wherein:

said second instruction includes an immediate data field having data corresponding to a number of bits in two sections of said single data word;

said data processing apparatus further comprises a mask generator having a mask control input receiving a mask control signal and an output connected to said third signal input of said arithmetic logic unit, said mask generator supplying to said third signal input of said arithmetic logic unit a mask having a number of right justified "1'"'"'s" corresponding to said mask control signal; and

said instruction decoder supplies data from said immediate data field of said second instruction to said rotate control input of said barrel rotator and to said mask control input of said mask generator in response to said second instruction.

18. The data processing apparatus of claim 14, further comprising:

a multiple flags register storing least significant bits equal to "0101";

an expand circuit having an input receiving said least significant bits of said multiple flags register and an output, said expand circuit generating a mask having four sections, all bits of each section having the same state as a corresponding bit of said least significant bits of said multiple flags register; and

said instruction decoder supplies data from said expand circuit to said third signal input of said arithmetic logic unit in response to said first instruction thereby supplying said first mask to said third signal input of said arithmetic logic unit.

19. The data processing apparatus of claim 14, wherein:

said data register file further includes

a second input bus connected to said data output of said barrel rotator for storing in a fifth instruction specified data register selected from among all of said plurality of data registers said data output of said barrel rotator.

20. The data processing system of claim 14, further comprising:

a multiple flags register storing least significant bits equal to "0101";

an expand circuit having an input receiving said least significant bits of said multiple flags register and an output, said expand circuit generating a mask having four sections, all bits of each section having the same state as a corresponding bit of said least significant bits of said multiple flags register; and

said instruction decoder supplies data from said expand circuit to said third signal input of said arithmetic logic unit in response to said first instruction thereby supplying said first mask to said third signal input of said arithmetic logic unit.

21. An data processing system forming a sum of data in four equal sections of a single data word comprising:

an data system bus transferring data and addresses;

a system memory connected to said data system bus, said system memory storing data and transferring data via said data system bus;

an data processor circuit connected to said data system bus, said data processor circuit including

a three input arithmetic logic unit having first, second and third signal inputs, a function input and an output;

a barrel rotator having a data input, a rotate control input receiving a rotate control signal, and a data output connected to said second signal input of the arithmetic logic unit, said barrel rotator left rotating data supplied to said data input an amount corresponding to said rotate control signal and supplying left rotated data to said second signal input of said arithmetic logic unit;

a data register file including

a plurality of data registers for storing data, said single data word initially stored in a first predetermined data register of said plurality of data registers,

a first output bus connected to said first signal input of said arithmetic logic unit for recalling from a first instruction specified data register selected from among all of said plurality of data registers the data stored therein,

a second output bus connected to said data input of said barrel rotator for recalling from a second instruction specified data register selected from among all of said plurality of data registers the data stored therein,

a third output bus for recalling from a third instruction specified data register selected from among all of said plurality of data registers the data stored therein,

a first input bus connected to said output of said arithmetic logic unit for storing in a fourth instruction specified data register selected from among all of said plurality of data registers said output of said arithmetic logic unit;

an instruction decoder responsive to a stream of instructions and connected to said plurality of data registers, said arithmetic logic unit and said barrel rotator, said instruction decoder responsive to a first instruction in which said first, second and fourth instruction specified data registers are identical and correspond to said first predetermined data register to

supply data stored in said first predetermined data register to said first signal input of said arithmetic logic unit and to said data input of said barrel rotator,

supply a first mask having "1'"'"'s" filling a first and a third section and "0'"'"'s" filling a second and a fourth section to said third signal input of said arithmetic logic unit,

supply a first rotate amount corresponding to one section of said single data word to said rotate control input of said barrel rotator,

control said arithmetic logic unit to perform addition of data received at said first and second signal inputs as masked by said first mask received at said third signal input, and

store an output of said arithmetic logic unit in said first predetermined data register,

said instruction decoder responsive to a second instruction in which said first, second and fourth instruction specified data registers are identical and correspond to said first predetermined data register to

supply data in said first predetermined data register to said first signal input of said arithmetic logic unit and to said data input of said barrel rotator,

supply a second mask having "1'"'"'s" filling said first and second sections and "0'"'"'s" filling said third and fourth sections to said third signal input of said arithmetic logic unit,

supply a second rotate amount corresponding to two sections of said single data word to said rotate control input of said barrel rotator,

control said arithmetic logic unit to perform addition of data received at said first and second signal inputs as masked by said second mask received at said third signal input, and

store said output of said arithmetic logic unit in said first predetermined data register.

22. The data processing system claimed in claim 21, wherein:

said data processor circuit wherein

said first mask is stored in a second predetermined data register of said plurality of data registers;

said third instruction specified data register of said first instruction corresponds to said second predetermined data register; and

said instruction decoder supplies data from said second predetermined data register via said third output bus of said data register file to said third signal input of said arithmetic logic unit in response to said first instruction thereby supplying said first mask to said third signal input of said arithmetic logic unit.

23. The data processing system claimed in claim 21, wherein:

said first rotate amount is stored in a predetermined data field in a third predetermined data register of said plurality of data registers; and

said instruction decoder supplies data from said predetermined data field of said third predetermined data register to said rotate control input of said barrel rotator in response to said first instruction.

24. The data processing system claimed in claim 21, wherein:

said data processor circuit wherein

said second instruction includes an immediate data field having data corresponding to a number of bits in two sections of said single data word;

said data processing apparatus further comprises a mask generator having a mask control input receiving a mask control signal and an output connected to said third signal input of said arithmetic logic unit, said mask generator supplying to said third signal input of said arithmetic logic unit a mask having a number of right justified "1'"'"'s" corresponding to said mask control signal; and

said instruction decoder supplies data from said immediate data field of said second instruction to said rotate control input of said barrel rotator and to said mask control input of said mask generator in response to said second instruction.

25. The data processing system of claim 21, wherein:

said data processor circuit further includes

a plurality of data memories connected to said data processor circuit,

an instruction memory supplying instructions to said data processor circuit, and

a transfer controller connected to said data system bus, each of said data memories and said instruction memory controlling data transfer between said system memory and said plurality of data memories and between said system memory and said instruction memory.

26. The data processing system of claim 25, wherein:

said data processor circuit further includes

at least one additional data processor circuit identical to said data processor circuit,

a plurality of additional data memories connected to each additional data processor circuit,

an additional instruction memory supplying instructions to each additional data processor circuit, and

said transfer controller is further connected to each of said additional data memories and each said additional instruction memory controlling data transfer between said system memory and said each of said additional data memories and between said system memory and each said additional instruction memory.

27. The data processing system of claim 26, wherein:

said data processor circuit including said data processor circuit, said data memories, said instruction memories, each of said additional data processor circuits, each of said additional data memories, each additional instruction memory and said transfer controller are formed on a single integrated circuit.

28. The data processing system of claim 25, wherein:

said data processor circuit further includes

a master data processor,

a plurality of master data memories connected to said master data processor,

at least one master instruction memory supplying instructions to said master data processor, and

said transfer controller is further connected to each of said master data memories and each said master instruction memory controlling data transfer between said system memory and said each of said master data memories and between said system memory and each said master instruction memory.

29. The data processing system of claim 28, wherein:

said data processor circuit including said data processor circuit, said data memories, said instruction memories, said master data processor, each of said master data memories, each master instruction memory and said transfer controller are formed on a single integrated circuit.

30. The data processor system of claim 21, wherein:

said system memory consists of an image memory storing image data in a plurality of pixels; and

said data processor system further comprising;

an image display unit connected to said image memory generating a visually perceivable output of an image consisting of a plurality of pixels stored in said image memory.

31. The data processor system of claim 30, further comprising:

a palette forming a connection between said image memory and said image display unit, said palette transforming pixels recalled from said image memory into video signals driving said image display unit;

and wherein said data processor circuit further includes

a frame controller connected to said palette controlling said palette transformation of pixels into video signals.

32. The data processor system of claim 21, wherein:

said system memory consists of an image memory storing image data in a plurality of pixels; and

said data processor system further comprising;

a printer connected to said image memory generating a printed output of an image consisting of a plurality of pixels stored in said image memory.

33. The data processor system of claim 32, wherein:

said printer consists of a color printer.

34. The data processor system of claim 32, further comprising:

a printer controller forming a connection between said image memory and said printer, said printer controller transforming pixels recalled from said image memory into print signals driving said printer;

and wherein said data processor circuit further includes

a frame controller connected to said print controller controlling said print controller transformation of pixels into print signals.

35. The data processor system of claim 21, wherein:

said system memory consists of an image memory storing image data in a plurality of pixels; and

said data processor system further comprising;

an imaging device connected to said image memory generating an image signal input.

36. The data processor system of claim 35, further comprising:

an image capture controller forming a connection between said imaging device and said image memory, said image capture controller transforming said image signal into pixels supplied for storage in said image memory;

and wherein said data processor circuit further includes

a frame controller connected to said image capture controller controlling said image capture controller transformation of said image signal into pixels.

37. The data processor system of claim 21, further comprising:

a modem connected to said data system bus and to a communications line.

38. The data processor system of claim 21, further comprising:

a host processing system connected to said data system bus.

39. The data processor system of claim 38, further comprising:

a host system bus connected to said host processing system transferring data and addresses; and

at least one host peripheral connected to said host system bus.

40. The data processing system of claim 21, wherein:

said data register file further includes

a second input bus connected to said data output of said barrel rotator for storing in a fifth instruction specified data register selected from among all of said plurality of data registers said data output of said barrel rotator.

41. A method for forming a summation comprising the steps of:

forming a plurality of partial sums in plural equal sections of a single data word employing an arithmetic logic unit selectively dividable into said plural equal sections; and

forming a sum of said plurality of partial sums in said sections of said data word by repeatedly

forming a mask having bits of a first digital state filling odd alternate portions and bits of a second digital state filling even alternate portions, said second digital state being opposite to said first digital state, said portion initially having a size equal to a section;

masking a prior sum data word by the mask thereby forming a masked prior sum data word, the single data word being a first prior sum data word;

rotating the prior sum data word by one portion;

masking the rotated prior sum data word by the mask thereby forming a masked rotated prior sum data word;

summing the masked prior sum data word and the masked rotated prior sum data word, thereby forming a sum data word; and

said steps of masking the prior sum data word, rotating the prior sum data word, masking the rotated prior sum data word and summing the prior sum masked data word and the rotated prior sum masked data word occur during a single data processor pipeline stage for each repetition in a three input arithmetic logic unit, said three input arithmetic logic unit having a first input receiving the prior sum data word, a second input receiving the rotated prior sum data word, a third input receiving the Mth mask and an output generating the summed prior sum masked data word and rotated prior sum masked data word;

doubling said size of each of said portions for a next repetition, until all sections are summed.

42. The method of claim 41, wherein:

said step of masking the prior sum data word consists of forming the logical AND of the mask and the prior sum data word; and

said step of masking the rotated prior sum data word consists of forming the logical AND of the mask and the rotated prior sum data word.

43. The method of claim 41, wherein:

said step of rotating the prior sum data word occurs in a barrel rotator, said barrel rotator having a data input, a rotate control input receiving a rotate control signal, and a data output.

44. The method of claim 41, wherein:

each of said masks has said first digital state equal to "1" and said second digital state equal to "0".