Method and apparatus for implementing a single cycle operation in a data processing system

• US 20030028844A1
• Filed: 06/21/2001
• Published: 02/06/2003
• Est. Priority Date: 06/21/2001
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Arc International (Synopsys Incorporated)
• Inventors: Coombs, Robert Anthony
• Granted Patent: US 6,848,074 B2
• Time in Patent Office: Days
• US Class Current: 714/796
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: H03M 13/4107 implementing add, compare, select [ACS] operations
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing
• CPC Class Codes: H03M 13/6505 Memory efficient implementations
• CPC Class Codes: H03M 13/6569 Implementation on processors, e.g. DSPs, or software implementations

Abstract

An improved method and apparatus for performing single-cycle operations (such as Viterbi decode) in digital processors is disclosed. In one aspect, the invention comprises methods for storing (“packing”) old and new metric data in memory that cooperate with a single operand instruction adapted to perform single cycle calculations such as the Viterbi butterfly. Accordingly, such calculations can be computed effectively in software in a single cycle. In another aspect, an improved memory addressing mode is used to write back two new output results at the completion of instruction execution. The improved packing of state metrics in memory, single operand instruction, and addressing mode can advantageously be integrated into any processor (e.g., DSP, RISC-DSP, or configurable processor) with appropriate memory. The user of such a processor may accordingly write software using the single operand instruction to perform Viterbi decode with the efficiency comparable to a dedicated hardware implementation.

Claims

1. A method for performing an add-compare-select butterfly operation for implementing a Viterbi decoder in a processor having an XY memory and extension arithmetic logic unit (ALU) associated therewith, comprising:

disposing old path metrics in said XY memory;

providing a single operand add-compare-select (ACS) instruction within the instruction set of said processor, said instruction having at least one short immediate (shimm) data field;

providing said old path metrics as inputs to said extension ALU;

controlling at least a portion of the operation of said extension ALU using said at least one shimm field; and

providing at least one addressing mode for said XY memory that allows new path metrics to be written back to XY memory subsequent to execution of said ACS instruction.

2. A method for performing an operation in a processor having a memory associated therewith, said memory being functionally partitionable into at least two components, said processor having an arithmetic logic unit (ALU) associated therewith, comprising:

disposing first metrics associated with said operation in said memory;

providing a single operand instruction within said processor'"'"'s instruction set;

providing said first metrics to said ALU;

controlling at least a portion of the operation of said ALU using at least one data field of said instruction; and

providing at least one addressing mode for said memory that allows at least second metrics of said operation to be written back to said memory subsequent to execution of said instruction.

3. The method of claim 2, wherein said act of disposing comprises:

arranging said path metrics in said memory such that two consecutive old metric values are packed into a single multi-bit value of a first or second component of said memory.

4. The method of claim 3, wherein said act of disposing further comprises arranging said path metrics such that one-half of the path metrics are disposed in a first component of said memory, and one-half the path metrics are disposed in a second component.

5. The method of claim 4, wherein first and second path metrics are stored in said first memory component at a first address, and the 2^K−

2 and 2<sup>K−

2+1</sup> path metrics are stored in said second memory component also at said first address, wherein “

K”

comprises the constraint length of the encoding algorithm.

6. The method of claim 2, wherein said act of providing a single operand instruction comprises:

defining an add-compare-select (ACS) instruction, said instruction having an instruction format, said format comprising a unique operational code (opcode);

describing the required functionality of the ACS instruction in a hardware description language (HDL);

simulating the ACS instruction with the host data processor; and

synthesizing the HDL to a technology-related netlist.

7. The method of claim 2, wherein the act of providing at least one addressing mode comprises describing in HDL said at least one addressing mode, said mode being used in the writeback of new metric data to said memory following execution of said single operand instruction.

8. The method of claim 7, wherein said single operand instruction comprises and ACS instruction, and said act of writeback comprises:

writing a first result of said execution of said ACS instruction to a first address within a first component of said memory; and

writing a first result of said execution of said ACS instruction to said first address within a second component of said memory.

9. The method of claim 7, wherein said act of providing at least one address mode further comprises:

analyzing said HDL;

simulating said HDL with the host processor and the ACS instruction; and

synthesizing said HDL to a technology-related netlist.

10. The method of claim 2, further comprising:

providing a computer program, at least a portion of said program being rendered in a high-level programming language and incorporating at least one of said single operand instructions;

determining at least one local distance value;

storing said at least one local distance value in at least one extension register, said at least one extension register being operatively coupled to said arithmetic logic unit (ALU);

initializing a plurality of metric buffers in said memory;

reading old metric values using at least one pointer;

providing metric updates using at least said single operand instruction; and

writing back said metric updates to said memory using said at least one addressing mode.

11. A data processor, comprising:

a multi-stage instruction pipeline;

an instruction set architecture having a plurality of instructions adapted to run on said processor in said pipeline, at least one of said plurality of instructions comprising a single operand instruction;

a plurality of extension registers;

an arithmetic logic unit (ALU) operatively coupled to at least a portion of said plurality of extension registers; and

wherein said processor further comprises at least one addressing mode adapted for addressing an associated storage device, said at least one mode being further adapted to write back at least one metric to said storage device subsequent to execution of said single operand instruction.

12. The processor of claim 11, wherein said single operand instruction comprises an add-compare-select instruction having a plurality of data fields.

13. The processor of claim 12, where at least one of said plurality of data fields is used to control the operation of said ALU.

14. The processor of claim 13, wherein said ALU comprises at least one multiplexer and at least one add-subtract unit.

15. The processor of claim 14, wherein said ALU comprises four multiplexers and four add/subtract units, each of said add/subtract units receiving said single operand as one input, and the output of the corresponding one of said four multiplexers as a second input.

16. The processor of claim 15, wherein each of said multiplexers comprises at least two inputs, said at least two inputs comprising values stored in said extension registers.

17. The processor of claim 14, wherein said at least one multiplexer and said at least one add/subtract unit are controlled at least in part by immediate (imm) bits present in said at least one data field of said instruction.

18. The processor of claim 15, wherein said ALU further comprises compare-select logic adapted to compare the output of at least two of said add/subtract units, and select at least one thereof as the output of said compare-select logic.

19. The processor of claim 18, further comprising at least one transition register, wherein the output of the compare portion of said compare-select logic is stored within said at least one transition register.

20. The processor of claim 11, wherein said ALU is disposed substantially within the third (execution) stage of said pipeline.

21. An arithmetic logic unit adapted for use with an extended data processor architecture, comprising:

a plurality of multiplexers;

a plurality of arithmetic operation units, each of said arithmetic operation units receiving a single operand as one input, and the output of a corresponding one of said plurality of multiplexers as a second input.

22. The logic unit of claim 21, wherein said logic unit is disposed substantially within the third (execution) stage of said pipeline.

23. The logic unit of claim 21, wherein each of said plurality of multiplexers comprises at least two inputs, said at least two inputs comprising values stored in extension registers of said data processor.

24. The logic unit of claim 21, wherein said at least one multiplexer and said at least one arithmetic operation unit are controlled at least in part by immediate (imm) bits present in at least one data field of a single operand instruction.

25. The logic unit of claim 24, wherein said arithmetic operation units comprise add/subtract units, said logic unit further comprising compare-select logic adapted to compare the output of at least two of said add/subtract units, and select at least one thereof as the output of said compare-select logic.

26. The logic unit of claim 25, further comprising at least one transition register, wherein the output of the compare portion of said compare-select logic is stored within said at least one transition register.

27. A method of generating a design for an extended digital processor, said processor being optimized for performance of at least one function, comprising:

defining at least one single operand instruction in a computer language;

generating a computer program utilizing said at least one single operand instruction, said program being adapted to perform said at least one function;

simulating the operation of said computer program;

defining at least one hardware configuration adapted for implementing said at least one instruction to form at least one hardware description language (HDL) definition; and

generating the design of said extended processor based at least in part on said at least one HDL definition.

28. The method of claim 27, further comprising synthesizing a netlist to a target technology based at least in part on said design.

29. The method of claim 27, wherein said act of defining said at least one hardware configuration comprises defining (i) at least one extension register, and (ii) at least one addressing mode adapted for use with said at least one single operand instruction.

30. The method of claim 29, further comprising co-simulating said at least one HDL definition with said computer program.

31. The method of claim 27, wherein the act of generating a computer program further comprises adapting said program to dispose path metrics within said memory such that a first portion of the path metrics are disposed in a first component of said memory, and a second portion of the path metrics are disposed in a second component of said memory.

32. The method of claim 31, wherein the act of disposing path metrics within said memory comprises disposing one-half of said metrics in X memory, and the other one-half of said metrics in Y memory.

33. The method of claim 31, further comprising adapting said extended processor and computer program to utilize:

(i) a writeback addressing mode; and

(ii) user-defined immediate data within said at least one single operand instruction;

to control the ALU of said processor.

34. The method of claim 27, further comprising adapting said extended processor and computer program to provide:

a writeback addressing mode; and

user-defined immediate data within said at least one single operand instruction;

said write-back mode and user-defined immediate data being used for controlling the ALU of said processor.

35. The method of claim 27, further comprising:

defining an extension ALU in a high level programming language; and

compiling as a dynamic link library (DLL) to an instruction set simulator.

36. The method of claim 28, further comprising processing said netlist using a second computer program to generate at least one file, said at least one file being useful in configuring an integrated circuit.

37. Apparatus for performing at least one arithmetic operation in a data processor, comprising:

a plurality of multiplexers each having a plurality of inputs and at least one output;

a plurality of arithmetic units, each of said arithmetic units receiving a single operand from at least one single-operand instruction as one input thereto, and said at least one output of a corresponding one of said plurality of multiplexers as a second input;

wherein each of said plurality of arithmetic units are controlled at least in part by data present in said at least one single operand instruction.

38. The apparatus of claim 37, wherein said data comprises short immediate (shimm) bits of said at least one instruction.

39. The apparatus of claim 37, wherein said plurality of arithmetic units each comprise addition/subtraction units.

40. The apparatus of claim 39, further comprising a plurality of extension registers, and wherein at least two of said plurality of inputs to each of said plurality of multiplexers comprise values stored in said extension registers.

41. The apparatus of claim 37, further comprising compare-select logic adapted to compare the outputs of at least two of said plurality of arithmetic units, and select at least one of said outputs as the output of said compare-select logic.

42. The apparatus of claim 41, wherein said plurality of arithmetic units comprise addition/subtraction units, and said at least one single-operand instruction comprises and add-compare-select (ACS) instruction.

43. The apparatus of claim 42, wherein said plurality of multiplexers comprises four multiplexers, said plurality of addition/subtraction units comprises four units, and said compare-select logic comprises at least two channels, each of said channels adapted to receive the output of two of said four addition subtraction units.

44. The apparatus of claim 42, wherein said ACS instruction comprises:

a first sliding window register with N-bit split writeback mode for the destination register; and

a second sliding window register with a standard incrementing 2×

N-bit read mode.

45. Data processor arithmetic logic unit apparatus, comprising:

at least one operand bus adapted to carry at least one operand thereon;

a plurality of constant busses each adapted to carry at least one value;

at least one control bus adapted to carry at least one control signal thereon;

a plurality of selection units, each of said units having a plurality of inputs and at least one output, at least one of said plurality of inputs comprising one of said constant busses, each of said selection units being adapted to multiplex between said plurality of inputs, the control of said multiplex function being related at least in part to said control signal present on said control bus;

a plurality of arithmetic units, each of said arithmetic units having as inputs (i) at least a portion of said at least one operand bus, and (ii) said at least one output of at least one of said selection units, the control of said arithmetic units being related at least in part to a signal present on said control bus;

at least one compare unit, said at least one compare unit having as an input the output of at least one of said arithmetic units, said at least one compare unit further having an output; and

at least one result multiplexer, said at least one multiplexer having the same inputs as the respective one of said at least one compare unit, said at least one result multiplexer being controlled by said output of said respective one of said at least one compare unit.

46. The apparatus of claim 45, further comprising a plurality of registers adapted for holding respective ones of said values carried on said constant busses.

47. The apparatus of claim 45, further comprising at least one transition shift register adapted to receive at least a portion of the output of said at least one compare unit, said at least portion being related to the operation of said apparatus with respect to a trellis calculation.

48. The apparatus of claim 45, wherein said apparatus is utilized within a Single Instruction Multiple Data (SIMD) data processor, said apparatus and said SIMD processor being adapted to perform multiple butterfly calculations in parallel using a single software instruction to control its operation.

49. The apparatus of claim 45, wherein said apparatus is disposed within a data processor and adapted to complete in a single clock cycle of said processor.

50. The apparatus of claim 45, further comprising a pipeline delay stage, said pipeline delay stage allowing use of an increased clock speed using multi cycle operation.

51. A method of processing metrics, comprising:

storing a first portion of input metrics in a first portion of a storage device, said first portion of said storage device having a data width of A bits;

storing a second portion of said input metrics in a second portion of said storage device, said second portion of said storage device having a data width of B bits; and

using a single pointer to read said first and second portions of said input metrics from said first and second portions of said storage device.

52. The method of claim 51, wherein A=B=2×

N-bits wide, and two input metric values of width N-bits are packed into each of 2×

N-bit wide first and second portions of said storage device.

53. The method of claim 52, where N=16.

54. The method of claim 51, further comprising:

providing the first portion of said input metrics as an input to a single operand instruction; and

incrementing said pointer at the end of the execution of said instruction to point to the next portion of said input metrics.

55. The method of claim 54, further comprising using a second pointer to read said second portion of said input metrics from said second portion of said memory, said second portion of said input metrics being read subsequent to said first portion.

56. The method of claim 51, wherein the acts of storing said first and second portions of said result metrics comprises using an N-bit addressing mode comprising half word width of first or second memory portions, and storing said first portion at an address [b] in said first portion of said storage device, and concurrently storing said second portion of said input metrics at address [b] in said second portion of said storage device.

57. The method of claim 51, further comprising:

reading metrics old(x) and old(x+1) from one of said portions of said storage device;

performing at least one arithmetic operation thereon to produce a result;

splitting said result into first and second result metric portions; and

storing said first and second result metric in a new metric buffer, consisting of said first and second memory portions;

arranging the first and second result metrics, using a single address pointer, so that said first result portion stored in a first portion of the new metric buffer and said second result portion stored in a second portion of the new metric buffer are in the same relative positions as old(x) and old(x<sup>k−

2</sup>+1) were in said storage device.

58. Apparatus for performing at least one arithmetic operation in a data processor, comprising:

a plurality of means for multiplexing, each of said means having a plurality of inputs and at least one output;

a plurality of arithmetic means, each of said arithmetic means receiving a single operand from at least one single-operand instruction means as one input thereto, and said at least one output of a corresponding one of said plurality of means for multiplexing as a second input;

wherein each of said plurality of arithmetic means are controlled at least in part by data present in said at least one single operand instruction means.

59. Data processing means, comprising:

a multi-stage instruction pipeline means;

an instruction set architecture having a plurality of instructions adapted to run on said processor in said pipeline, at least one of said plurality of instructions comprising a single operand instruction means;

a plurality of means for storing data bits;

an arithmetic logic unit means operatively coupled to at least a portion of said plurality of means for storing data bits; and

wherein said processor means further comprises at least one addressing mode adapted for addressing an associated means for storing data, said at least one mode being further adapted to write back at least one metric to said means for storing data subsequent to execution of said single operand instruction means.

60. A method of processing metrics, comprising the steps of:

storing a first portion of input metrics in a first portion of a storage device for subsequent use as an input, said first portion of said storage device having a data width of A bits;

storing a second portion of said input metrics in a second portion of said storage device for subsequent use as an input, said second portion of said storage device having a data width of B bits; and

using a single pointer to read multiple input metrics packed into said first or second portions of said input metrics from said first or second portions of said storage device.