Method and system for encoding variable length packets with variable instruction sizes

Techniques for processing transmissions in a communications (e.g., CDMA) system. The method and system encode and process instructions of mixed lengths (e.g., 16 bits and 32 bits) and instruction packets including instructions of mixed lengths. This includes encoding a plurality of instructions of a first length and a plurality of instructions of a second length. The method and system encode a header having at least one instruction length bit. The instruction bit distinguishes between instructions of the first length and instructions of the second length for an associated DSP to process in a mixed stream. The method and system distinguish between the instructions of the first length and the instructions of the second length according to the contents of the instruction length bits. The header further includes bits for distinguishing between instructions of varying lengths in an instruction packet.

FIELD

The disclosed subject matter relates to data communications. More particularly, this disclosure relates to a novel and improved method and system for encoding variable length packets with variable instruction sizes.

DESCRIPTION OF THE RELATED ART

A modern day communications system must support a variety of applications. One such communications system is a code division multiple access (CDMA) system that supports voice and data communication between users over a satellite or terrestrial link. The use of CDMA techniques in a multiple access communication system is disclosed in U.S. Pat. No. 4,901,307, entitled “SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS,” and U.S. Pat. No. 5,103,459, entitled “SYSTEM AND METHOD FOR GENERATING WAVEFORMS IN A CDMA CELLULAR TELEHANDSET SYSTEM,” both assigned to the assignee of the claimed subject matter.

A CDMA system is typically designed to conform to one or more standards. One such first generation standard is the “TIA/EIA/IS-95 Terminal-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System,” hereinafter referred to as the IS-95standard. The IS-95CDMA systems are able to transmit voice data and packet data. A newer generation standard that can more efficiently transmit packet data is offered by a consortium named “3rdGeneration Partnership Project” (3GPP) and embodied in a set of documents including Document Nos. 3G TS 25.211, 3G TS 25.212, 3G TS 25.213, and 3G TS 25.214, which are readily available to the public. The 3GPP standard is hereinafter referred to as the W-CDMA standard.

Digital signal processors (DSPs) are frequently being used in wireless handsets complying with the above standards. In particular, wireless handsets are requiring and increasingly will require that their DSP process user orientation, scientific, and multimedia applications, as well as many other types of applications for which a single approach to multithreaded operations provides a workable solution. Moreover, the resource requirements may change widely and dynamically for applications such as television broadcasts, streaming message tickers, electronic mail (including messages with attached documents), as well as resident applications, such as photography and PDA applications, all from the same DSP.

One significant problem to solve in such DSPs is to delineate the instruction size for the instructions that DSP must execute. On the one hand high performance demands instructions to be of a large size, e.g., 32-bits or more in length. On the other hand, there is the need for small code size, e.g., 16-bits in length. In order to achieve small code size, there is the need to have a mix of short 16-bit instructions and large 32-bit instructions. The VLIW (Very Long Instruction Word) class of DSP machines also encodes groups of instructions to determine which instructions may be executed in parallel. Achieving an understanding of which instructions may be processed in parallel requires both a delineation of the instruction size (i.e., 16-bit or 32-bit instructions) as well as the packet size (i.e., which instructions are group together to form a particular packet). When there are mixed instruction sizes, the machine must delineate quickly which instructions are 16-bit instructions and which are 32-bit instructions. If this is difficult to determine, a number of other problems arise in DSP operation.

One classical approach to determining instruction size is known as instruction serialization. In such schemes, it is necessary to determine serially the size of each instruction. Thus, in order to determine the size of any instruction, it is necessary to know the size of the all preceding instructions. If there are many instructions, the requirement to determine serially the size of all preceding instructions can be limiting. Accordingly, a need exists for a method and system that allows for parsing of instructions in a manner other than serially, for distinguishing between 16-bit and 32-bit instructions.

Another problem with instruction size delineation has to do with packet delineation. Packet delineation involves using a number of instructions in parallel. The challenge is to delineate which instructions to group together. In one known DSP architecture, for example, all instructions are of 32-bit length. In such an architecture, there is no need to delineate size differences. There is, however, the need to delineate the association of instructions in packets. This permits determining which packets are grouped together for execution as an instruction packet. Presently, however, no known way exists to rapidly and efficiently delineate packet sizes for DSPs using mixed instructions. Accordingly, a further need exists for a method and system for delineating packet sizes in DSPs executing instruction packets of varying lengths that may include variable length instructions.

A further need exists for a method and system that not only avoids the problems associated with serially determining the size of mixed length instructions, but also provides for efficient packet delineation in a DSP capable of supporting many different wireless handset applications.

SUMMARY

Techniques for encoding variable length instructions and packets with variable instruction sizes are disclosed, which techniques improve both the operation of a digital signal processor and the efficient use of digital signal processor instructions for processing increasingly robust software applications for personal computers, personal digital assistants, wireless handsets, and similar electronic devices, as well as increasing the associated digital processor speed and service quality.

According to one aspect of the disclosed subject matter, there is provided a method and a system for encoding and processing instructions and packets of instructions of mixed lengths (e.g., 16 bits and 32 bits). The method includes the steps of and the system includes the structures for encoding a plurality of instructions of a first length (e.g., 16 bits) and a plurality of instructions of a second length (e.g., 32 bits). The method and system encode a header having at least one instruction length bit. The instruction bit distinguishes between the instructions of the first length and the instructions of the second length. The DSP processes the instructions in a mixed stream of instructions of the first length and the instructions of the second length. The method and system distinguish between each of the instructions of the first length and the instructions of the second length according to the contents of the instruction length bits.

The disclosed subject matter further includes in the header predetermined bits for designating the instructions in a packet. Thus, by including such functional bits in the header, the method and system can specify or distinguish between instructions of varying lengths as well as the number of such instructions in an instruction packet. As such, here appears a method and system that not only avoids the problems associated with serially determining the size of mixed length instructions, but also provides for efficient packet delineation in a DSP capable of supporting many different wireless handset applications.

These and other advantages of the disclosed subject matter, as well as additional novel features, will be apparent from the description provided herein. The intent of this summary is not to be a comprehensive description of the claimed subject matter, but rather to provide a short overview of some of the subject matter's functionality. Other systems, methods, features and advantages here provided will become apparent to one with skill in the art upon examination of the following FIGUREs and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the accompanying claims.

DETAILED DESCRIPTION OF THE SPECIFIC EMBODIMENTS

FIG. 1is a simplified block diagram of a communications system10that can implement the presented embodiments. At a transmitter unit12, data is sent, typically in blocks, from a data source14to a transmit (TX) data processor16that formats, codes, and processes the data to generate one or more analog signals. The analog signals are then provided to a transmitter (TMTR)18that modulates, filters, amplifies, and up converts the baseband signals to generate a modulated signal. The modulated signal is then transmitted via an antenna20to one or more receiver units.

At a receiver unit22, the transmitted signal is received by an antenna24and provided to a receiver (RCVR)26. Within receiver26, the received signal is amplified, filtered, down converted, demodulated, and digitized to generate in phase (I) and (Q) samples. The samples are then decoded and processed by a receive (RX) data processor28to recover the transmitted data. The decoding and processing at receiver unit22are performed in a manner complementary to the coding and processing performed at transmitter unit12. The recovered data is then provided to a data sink30.

The signal processing described above supports transmissions of voice, video, packet data, messaging, and other types of communication in one direction. A bi-directional communications system supports two-way data transmission. However, the signal processing for the other direction is not shown inFIG. 1for simplicity. Communications system10can be a code division multiple access (CDMA) system, a time division multiple access (TDMA) communications system (e.g., a GSM system), a frequency division multiple access (FDMA) communications system, or other multiple access communications system that supports voice and data communication between users over a terrestrial link. In a specific embodiment, communications system10is a CDMA system that conforms to the W-CDMA standard.

FIG. 2illustrates DSP40architecture that may serve as the transmit data processor16and receive data processor28ofFIG. 1. Recognize that DSP40only represents one embodiment among a great many of possible digital signal processor embodiments that may effectively use the teachings and concepts here presented. In DSP40, therefore, threads T0through T5(reference numerals42through52), contain sets of instructions from different threads. Circuit54represents the instruction access mechanism and is used for fetching instructions for threads T0through T5. Instructions for circuit54are queued into instruction queue56. Instructions in instruction queue56are ready to be issued into processor pipeline66(see below). From instruction queue56, a single thread, e.g., thread T0, may be selected by issue logic circuit58. Register file60of selected thread is read and read data is sent to execution data paths62for SLOT0through SLOT3. Slot0through SLOT3, in this example, provide for the packet grouping combination employed in the present embodiment.

Output from execution data paths62goes to register file write circuit64, also configured to accommodate individual threads T0through T5, for returning the results from the operations of DSP40. Thus, the data path from circuit54and before to register file write circuit64being portioned according to the various threads forms a processing pipeline66.

The present embodiment may employ a hybrid of a heterogeneous element processor (HEP) system using a single microprocessor with up to six threads, T0through T5. Processor pipeline66has six stages, matching the minimum number of processor cycles necessary to fetch a data item from circuit54to registers60and64. DSP40concurrently executes instructions of different threads T0through T5within a processor pipeline66. That is, DSP40provides six independent program counters, an internal tagging mechanism to distinguish instructions of threads T0through T5within processor pipeline66, and a mechanism that triggers a thread switch. Thread-switch overhead varies from zero to only a few cycles.

DSP40, therefore, provides a general-purpose digital signal processor designed for high-performance and low-power across a wide variety of signal, image, and video processing applications.FIG. 3provides a brief overview of the DSP40architecture, including key aspects of the associated instruction set architecture for one manifestation of the disclosed subject matter. Implementations of the DSP40architecture support interleaved multithreading (IMT). In this execution model, the hardware supports concurrent execution of multiple hardware threads T0through T5by interleaving instructions from different threads in the pipeline. This feature allows DSP40to include an aggressive clock frequency while still maintaining high core and memory utilization. IMT provides high throughput without the need for expensive compensation mechanisms such as out-of-order execution, extensive forwarding networks, and so on. Moreover, the DSP40may include variations of IMT, such as those variations and novel approaches disclosed in the commonly-assigned U.S. Patent Applications by M. Ahmed, et al, and entitled “Variable Interleaved Multithreaded Processor Method and System” and “Method and System for Variable Thread Allocation and Switching in a Multithreaded Processor.”

The subject matter here disclosed deals with the execution model of a single thread. The software model of IMT can be thought of as a shared memory multiprocessor. A single thread sees a complete uni-processor DSP40with all registers and instructions available. Through coherent shared memory facilities, this thread is able to communicate and synchronize with other threads. Whether these other threads are running on the same processor or another processor is largely transparent to user-level software.

FIG. 3, therefore, provides an architecture block diagram of one embodiment of a programming model for a single thread.FIG. 3shows one embodiment of a block diagram for instruction set architectural (ISA)70of DSP40, which includes unified byte-addressable memory72. Memory72provides mixed 16-bit and 32-bit instructions to sequencer74. Memory72may include a computer usable medium having computer readable program code for proccessing the 16-bit and 32-bit instructions on DSP40. There are two register files, including general register76and control register78. Sequencer74provides hybrid two-way superscaler instructions and four-way VLIW instructions to vector shift unit80, vector MAC unit82, load unit84, and load/store unit86. The DSP40architecture, therefore, features a unified memory72and a single unified register file. Mixed 16- and 32-bit instructions can be issued in parrallel, up to four at a time, in one embodiment. ISA70, furthermore, supports moving two 64-bit double words from memory to registers each cycle.

Memory72, general register76, and control register78of DSP40support a single 32-bit address space that holds both instructions and data operating in little endian mode. General register76holds thirty-two 32-bit registers which can be accessed as single registers, or as aligned 64-bit pairs. General register76holds all pointer, scalar, vector, and accumulator data and provides flexibility for service as a compiler target. Control register78holds special-purpose registers such as program counter, status register.

ISA70features a hybrid execution model that mixes the advantages of superscalar and VLIW execution. Superscalar issue has the advantage that no software information is needed to find independent instructions. There is no added code size or encoding inefficiencies to provide multi-issue execution. Additionally, superscalar issue can find parallel instructions over branch boundaries which can be difficult for a compiler. However, superscalar issue becomes expensive in hardware beyond dual issue.

The advantage of the VLIW execution is that the software may identify many more than two instructions for parallel execution, especially in software pipelined loops which are typical of DSP code. VLIW is an inexpensive way to provide wide issue capability. ISA70, therefore, combines the strengths of both execution models by creating a hybrid model. The execution model of ISA70communicates VLIW packet information for packets of three or more instructions. For parallelism of one and two instructions, ISA70is responsible for multi-instruction execution via dual superscalar issue. In this way, the architecture and associated micro-architecture can deliver wide issue parallelism with a minimal code size penalty. Parallelism over branch boundaries in control code can also be exploited.

As described in further detail below, instructions are encoded using either 16-bit instructions or 32-bit instructions. The two instruction sizes can be freely mixed in a program. These mixed size instructions can be packetized in groups for parallel execution. The packets may be of variable size. The 16-bit instruction set is chosen to carefully match the needs of a compiler generating dense control code.

ISA70, furthermore, combines a RISC-like scalar instruction set which provides excellent support to the compiler and a DSP-oriented instruction set which provides a rich set of operations for signal processing applications. Within DSP40, ISA70code is upwards binary compatible. This means that binaries written for a low-end implementation will run untouched on a high-end implementation. DSP40, using ISA70, specifically supports following classes of applications: (1) communications signal-processing (e.g., modems); (2) video processing (e.g., H.264 format); (3) image processing; (4) audio processing; (5) 3-D graphics front-end software; and (6) supporting control code, protocol stacks, RTOS, etc.

With the disclosed subject matter, instruction encoding includes a binary encoding scheme for instructions and packets of grouped instructions.FIG. 4illustrates instruction size parsing diagram90for the present embodiment. In particular, 16-bit halfwords92include most significant bits94, which serve as instruction length bits for indicating the length of halfwords92. Thus, with values of “01,” “10,” “11,” halfwords92are identified to be 16 bits in length. Note, also, that if a halfword92is in a packet (described below) and instruction length bits 94 have the “00” value, then the length could be 16 bits in this implementation. Alternatively, if the 16-bit halfword is not in a packet and the instruction length bit has the value “00,” then the instruction length is 32 bits. This is shown in 16-bit halfwords96, which are part of 32-bit instructions98. In particular, 32-bit instructions98, after instruction length bits100, which all have values of “00,” all instruction bits102have values of “01,” “10,” and “11”. Moreover, in the illustrated embodiment, the 32-bit instruction102instruction bits106of value “00” and instruction bits108of value “00.” The most significant bits of this 32-bit instruction104may include uses other than for length designation, for example.

In order to achieve optimal code density, ISA70supports mixed 16-bit instructions92and 32-bit instructions98. These instructions can be freely mixed together and can optionally be grouped together in packets for parallel execution. The 16-bit instructions92have access to a restricted set of registers and only the most frequent opcodes are available in 16-bit format. The 16-bit instructions92are typically available in two-operand source destructive format. The instructions chosen for 16-bit formation are based on the statistically most frequent instructions from compiled code.

The two most significant bits (MSBs) of each 16-bit halfword92and96, therefore, indicate the end of the instruction. Most 16-bit instructions92are subset versions of 32-bit instructions98. For example, in one embodiment, a 16-bit ADD immediate instruction has a shorter immediate and a more limited register range then the equivalent 32-bit ADD instruction. A certain class of 16-bit instructions92are available only inside a packet. These instructions are always subset versions of equivalent 32-bit instructions98. The 32-bit instructions98may be used inside or outside of a packet. These 32-bit instructions98are chosen to be the common instructions found inside packets. The 32-bit instructions98have access to all register resources and all opcodes and are presented in three-operand non-source destructive format.

With the present embodiment, instructions92and98may be grouped together to form packets110(FIG. 5) of independent instructions to be executed together and in parallel. How many and what type of instructions92and98may be grouped together is an architectural option that may depend, for example, on the particular implementation. For example, one version of DSP40supports up to four instructions grouped in a packet.

FIG. 5shows packet110to include packet header112associating with four parallel instructions114. Parallel instructions114include instruction0of 16 bits116, instruction1of 16 bits118, instruction2of 32 bits120, and instruction3of 16 bits122. Encoding of parallel instruction packets110in the present embodiment includes grouping of instructions into packets110of independent work. ISA70guarantees that all instructions in a group can be executed in parallel. Packets110are formed by pre-pending the independent instructions with packet header112which includes information about packet110. Packet header112is encoded as a 16-bit instruction. Architecturally grouped packet110, in the presented example, encodes four instructions. In the case there are less than four grouped instructions, a NOP instruction may be used in the unused slot.

There may be various rules for and restrictions on what types of instructions to group together and in what order they should appear in packets110. In general, packets110should be concerned with resource constraints, dependency constraints, and ordering constraints. Moreover, packets110may be defined to have parallel execution semantics. This means that the execution behavior of a packet110may be as follows: first, all instructions in the packet110may read their source registers in parallel; next, all instructions in the packet may execute in parallel; finally, all instructions in the packet may write their destination registers in parallel.

Consistent with the present disclosure, packets and single instructions may be freely mixed in code. A packet110should be considered as an atomic unit, in essence a large “instruction,” in the present embodiment. Similar to individual instructions, a packet110may execute to completion or not at all, i.e., a packet preferably never partially completes execution. If a packet causes a memory exception, for example, then the present embodiment establishes an exception point before the packet. Packets110may have a single PC address which is the address of the start of the packet. Preferably, it is illegal to branch into the middle of a packet110. Architecturally, packets110or single instructions92and98may execute to completion including updating all registers and memory before the next packet or instruction begins.

FIG. 6depicts, in further detail, packet header112encoding for one embodiment of the disclosed subject matter. In particular, of the 16 bits for packet header112, least significant bits124,126,128, and130relate, respectively and referring toFIG. 5, to the size of the instruction0116, instruction1118, instruction2120, and instruction3122. Packet header112further includes outer loop bit132and inner loop bit134, as well as packet header opcode136.

Packet header112, as can be seen, provides a unique 16-bit instruction that contains information about the packet, such as packet110. With packet header112, the least-significant four bits indicate the size of each of the four instructions (either 16 or 32-bits). Inner loop bit132and outer loop bit132may be used by a hardware looping mechanism of DSP40for marking packet110as the last in an inner or outer loop, respectively. The remaining bits138and140, marked “−” inFIG. 6, may be reserved for future expansion, in the presented embodiment, and are preferably set to zero.

In the presented embodiment, packet header112architecturally limits the maximum number of instructions in a packet to four. However, various ISA70versions may specify a 32-bit packet header which supports much wider issue.

When instructions are included in packet110, the “00” continuation pattern in the halfword MSBs is redundant information. This “00” marker is distinguishing between16and 32-bit instructions, which is the same information that is in the packet header. This fact is exploited by recycling the “00” pattern within a packet. For packetized instructions, the “00” pattern is used to encode 16-bit instructions that are only available inside a packet.

The present embodiment overcomes the size delineation problem of serial analysis, because packet header112bits specify the instruction size. The present embodiment overcomes the packet delineation problem of prior approaches by use of the header bits94and100for specifying the individual instruction size, which bits also permit determining the total packet size. The present embodiment also provides additional flexibility in that more information may be inserting into each instruction.

In summary, the disclosed subject matter provides a method and a system for encoding and processing instructions of mixed lengths (e.g., 16 bits and 32 bits). The method includes the steps of and the system includes the instructions and related structures for encoding a plurality of instructions of a first length92(e.g., 16 bits) and a plurality of instructions of a second length98(e.g., 32 bits). The method and system encode a header94and100having at least one instruction length bit. The instruction bit distinguishes between the instructions of the first length92and the instructions of the second length98. DSP40processes the instructions in a mixed stream of instructions of the first length92and the instructions of the second length98. The method and system distinguish between each of the instructions of the first length92and the instructions of the second length98according to the contents of the instruction length bits94and100.

The disclosed subject matter further includes specified bits in the header for designating the instructions in a packet. Thus, by including such bits in the header, the method and system can specify or distinguish between instructions of varying lengths as well as the number of such instructions in an instruction packet. As such, here appears a method and system that not only avoids the problems associated with serially determining the size of mixed length instructions, but also provides for efficient packet delineation in a DSP capable of supporting many different wireless handset applications.

The processing features and functions described herein can be implemented in various manners. For example, not only may DSP40perform the above-described operations, but also the present embodiments may be implemented in an application specific integrated circuit (ASIC), a microcontroller, a microprocessor, or other electronic circuits designed to perform the functions described herein. The foregoing description of the preferred embodiments, therefore, is provided to enable any person skilled in the art to make or use the claimed subject matter. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the innovative faculty. Thus, the claimed subject matter is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.