JP2003521072A - Improved apparatus and method for multithreaded signal processing - Google Patents

Abstract

Abstract: The system and circuit design method and apparatus, using its multi-thread representation, implement a general function definition (10), which comprises one or more corresponding kernel logic elements (18). May be profiled for parallel processing. Preferably, the communication (26), networking, or media processing function or algorithm (12) is functionally parsed and symbolically represented to identify one or more thread segments, each of which is Profiled using temporal and / or non-temporal functions according to one or more specific fixed, parameterized, programmable or reconfigurable logic kernels (14).

Description

Detailed Description of the Invention

TECHNICAL FIELD The present invention relates to electronic data and signal processing, and more particularly to high performance multi-thread information processing technology.

BACKGROUND OF THE INVENTION Conventional methods for achieving high performance in computing systems for digital information processing have centered around architectural designs that deliver higher levels of parallelism. This is typically accomplished through the design of processor and instruction set architectures that allow for hardware concurrency and software concurrency.

High performance is usually defined as the ability to perform very many operations per second. This figure of merit is strongly dependent on the type of operation, which is usually
Depends on the symmetric application type.

Conventional designs for high performance information handling systems typically rely on computer architecture principles to define some important attributes of a processing system:
Instruction set architecture refers to the actual programmer-managed set of instructions and serves as the boundary between hardware and software. Organization refers to the high-level aspects of computer design, such as memory system, bus structure, and internal CPU design. Hardware refers to a particular detailed logic design, circuit implementation, and packaging.

Three approaches are typically taken to achieve high performance, an attribute required in special-purpose (ie, built for specialized applications) processors: (1) Instruction level parallelism Processing: This approach utilizes parallel processing in hardware to provide for parallel threads of processing through the use of very long or vectored instruction words, the fields of which are decomposed into concurrency processing threads. be able to. The mechanism for utilizing this parallel processing may be implemented via a scheduler, which schedules the operation to one of several datapath processing units. This scheme has many drawbacks, including the difficulty of building a scheduler and identifying sufficient concurrency to achieve the desired throughput. (2) Superscaler technology: This approach is designed to achieve high performance.
Take advantage of granularity, high pipeline, single-threaded processing architecture.
This scheme may achieve very high performance, but only for a small class of operations. For operations that do not fit well into a particular datapath architecture, the performance of the superscaler design is significantly reduced. As such, the superscaler approach is not suitable for a wide range of applications involving high signal processing content. (3) Memory hierarchy technology: In order to hide the latency of memory access to slower memory, memory hierarchy technology effectively hides the latency of slower memory,
It has been used comprehensively, especially in microprocessor designs, to improve overall system performance by intelligently using fast memory, or cache, between the processor unit and slower memory.

Traditionally, multi-processor systems may employ multi-threaded processing to improve computational performance. Multi-threading is generally
Known as a computing resource utility, and an approach to enhance overall processing performance. However, common multi-threaded solutions are implemented using complex distributed or network computer nodes, which often cannot be easily reconfigured at lower logic or circuit levels, and which are multimode telecommunications. It is also not considered to address evolving functional issues such as algorithms or networking protocols. Therefore,
There is a need for improved multi-threading solutions.

DISCLOSURE OF THE INVENTION The present invention is a design and implementation methodology for multi-threaded digital information (signal or data representation) to improve functional (hereinafter “function”) performance. , Processor architecture, and system. Preferably, a general system design or function (hereinafter referred to as function) definition, algorithm, electronic signal or data file is provided first to include one or more multi-threaded representations. Such an initial prototype design or function may be temporally and / or non-temporally functional, in particular one or more corresponding, fixed, parametrizable, programmable or configurable. Logic unit or other equivalent functional signal processing kernel or element to be used or implemented functionally, profiled for parallel processing or similar processing in effect, or otherwise characterized You may be asked.

Preferably, the relatively complex system functions are pre-specified system design rules, mathematical operations, operations, for example for applications in digital communication and / or networking and / or media processing system design. Sequence, or parameters, and then symbolically or graphically one or more algorithms, specific sequences of operations, patterns of memory access, or segments (ie, single or multiple "threads"). Identified, each of which is optimized for operation using one or more specific fixed, parameterized, programmable or configurable logic units or kernel elements. Or regarding the implementation It may be profiled, constructed, or characterized. Such elements have structure and configurability (config
locality to profile sequencer / finite state machines and memory accesses, with structure and conformity determined through profiling, and data paths with urability) and to extract local memory properties. Is built by a local memory whose structure is determined by using Optionally, one or more kernel elements are fully implemented in software or programmable logic, or a combination thereof. Further, as described herein, the term "profiling" generally refers to the automation of one or more system or function modules to define one or more configurable structures associated with each module. And / or refers to manual processing.

BEST MODE FOR CARRYING OUT THE INVENTION The present invention provides an automated design or implementation for single or multi-threading or equivalent of digital data, signals or functional representations for improved processing performance. Enables processing of the divided processing. First, the system design or function definition,
An algorithm, electronic signal, or data file provides a constant single or multi-threaded representation, at which time one or more system design or function modules are profiled and constructed for parallel or concurrent processing. , Otherwise characterized.

For example, multithreaded prototypes are used in fixed, parameterizable, programmable, or configurable logic units or other signal processing kernels or elements, or otherwise May be implemented. Thus, complex system functions, such as digital communication, networking, or multimedia applications, may be analyzed according to system design rules, mathematical operations, sequences of operations, or parameters, and then fixed single or multi-valued. Thread algorithm,
It may be symbolically or graphically represented to identify a particular sequence of operations, patterns of memory access, or segments, where each thread is fixed, parameterized, programmable, Alternatively, configurable logic units or kernel elements are used to profile or characterize to optimize operation or implementation.

Optionally, the datapath structure is a profiling-determined single or multi-threaded element, a sequencer and / or equivalent finite state machine with a profiling-determined structure and configurability, and a memory Configured into local memory having a structure determined by profiling memory access and locality to extract properties.

As used herein, the term profiling generally refers to each module by selecting or assigning one or more functional elements or design objects, such as interconnects, signals, logic, circuits, etc. Refers to any computer automation and / or manual processing, translation or classification of one or more system or function modules to define or categorize one or more configurable structures associated with. Preferably, profiling is accomplished according to one or more previously and / or dynamically defined criteria or functional rule sets.

In general, in computer automation and / or manual development approaches, a single or multi-threaded design first provides a first level function definition that represents the prototype system, and other equivalent symbolic representations. Function levels are generated or processed by effectively profiling from them. In this hierarchical design scheme, the generated symbolic representation may identify certain threads associated with the system design, preferably at one or more function levels.

Each thread may be profiled for processing by a corresponding kernel element, and one or more common sets of operations may be for a given thread (eg, one-to-one, multiple-to-one, or one-to-one). To multiple threads to kernel relationships). Each thread further includes a sequence of arithmetic, control, and / or memory access operations, or sequences for each set of operators utilized to implement a system or function module, such as associated memory locations. Alternatively, it may be mapped to identify scheduling information.

Thus, using the system development methodology, a multi-threaded processing architecture allows one kernel element to process a certain function represented by the corresponding thread and another in the same prototype design. A kernel element may substantially include a set of kernel elements to handle other functions represented by other corresponding threads. In this split or distributed processing approach, each thread may be profiled separately or hierarchically for appropriate multi-level or function group processing. For example, a first level or group kernel element and a second level or group kernel element are associated with corresponding first and second threads in a function or system design, respectively.

In a typical system design for wireless code division multiple access (CDMA) communication applications, various kernels: front end processing (
For example, data switch selector, sample interpolation, etc .; chip rate processing (eg, sample epoch selection, matched filters, generic despreader, generic dechannelizer (gene).
ric dechannelizer), code generator, integration and dump, general-purpose searcher control (g
eneric searcher control, etc.); symbol sequence processing (eg, transport format decoder, dynamic spreading factor computer)
ter), high-speed Hadamard conversion, etc.); channel element processing (eg,
Alignment / Deskewing, Combiner,
Soft-decision computer, interpath interferen
ce equalizer), receive antenna diversity combiner (receive antenn
a diversity combiner, etc.); interleaving (eg, deinterleaver controller), and channel coding (
For example, a turbo decoder, a convolutional decoder, etc.) could be provided to provide various groups of functions.

In general, according to the present approach, one or more functions or system designs may be kernel kernels from which the corresponding threads are assembled, preferably through the present multi-threaded architecture, in a single processor architecture. By reparameterizing, reprogramming, or reconfiguring the element (ie, as determined by profiling techniques, as further described)
, And / or with which a thread may be effectively implemented by changing the sequence of operations implemented (ie, as determined by mapping and / or scheduling). The preferred embodiment is
Performing a function or system design in one or more heterogeneous and reconfigurable logic or kernel elements (ie, in accordance with so-called "DRL" processing, as further described herein).

FIG. 1 preferably illustrates one or more stand-alone or network computers, processors, engineering workstations, or suitable operating systems, user interfaces, storage management, communication interfaces and other computers. Top of the design methodology, function modules, and software and / or hardware tool architectures implemented in one or more electronic design automation platforms, including assisted design and other computing equipment with engineering tools. 1 is a general architecture or system block diagram showing an overview of levels. Preferably, the design methodology may serve to provide tool and processor implementations and architectures, or data files representing them, to enable system architectures such as network implementations.

As shown, first, one or more function definition files 10, such as a design netlist, or a high-level description language (C or HDL, etc.) 12 that defines one or more function modules or algorithms is manually created. Supplied or calculated automatically.
In accordance with one feature of the present implementation, the functionally selective profiling and mapping scheme 14 is processed or, particularly multi-threaded, to generate or provide one or more control and communication signals 26 and kernels 18. , Primitive 16
And function definition 10. In addition, profiling and mapping 14
Scheduling for the schedule operations table 20
Supply data. Control and communication signals are processed according to one or more pre-defined or selected sets of function rules or signal flags, such as communication semaphore 24. Various kernels 18 are processed and interconnected for implementation 22 in a reconfigurable form, eg, for multithreaded signal processing, as described herein.

The functional block diagrams of FIGS. 2A-B show a representative set of their physical implementation sets, including kernels 18, 28 and a schedule and allocate function 30. Preferably, one or more kernels 18 are associated with or correspond to profiled and mapped threads, and sequencer 3
2, reconfigurable implementation using the data path 34 and the memory 36.

Thus, according to the present system and circuit design methodology and / or computing device, a general function definition can be implemented using its single or multi-threaded representation, which can be one or more corresponding kernel logics. Elements (eg, one-to-multi, one-to-one, multi-to-one, or multi-to-multi kernel-to-thread relationships)
May be effectively profiled for parallel processing. For example, communication,
Networking or media processing functions or algorithms are functionally parsed and symbolically represented to identify one or more thread segments, each of which is one or more specifically designed fixed Profiled, or otherwise characterized, for optimized operation or implementation using a parameterized, programmable, or reconfigurable logic kernel.

The functional diagram depicted in FIG. 3 illustrates a typical heterogeneous, reconfigurable, multiprocessing array, where, for example, kernel 8 may implement a “small” granular thread function, And kernel 6 may implement a "large" granularity thread function. In this reconfigurable array, different levels of functional granularity, preferably attributes of the design function and corresponding kernels, are implemented or dynamically according to design requirements or profile mapping preferences. May be reconfigured.

For further explanation, the functional diagram of FIG. 4 illustrates single or multi-threading,
May be adopted according to this approach for implementation in a specified kernel,
Shows one or more representative or available configurable logics or functions,
They are, for example, reconfigurable logic or programmable function unit (PFU) 40 with programmable logic elements and switch matrices (eg encoding bit level operations), multiplexers, registers, adders, buffers etc. And a reconfigurable datapath 42 having a configurable signal flow through these elements (eg, to a dedicated datapath filter), and an address generator (eg, for an arithmetic convolution kernel), memory, memory address control, etc. Reconfigurable operations 44 and data (eg, for real-time operating system process management)
A reconfigurable control 46 having a memory, data path, program memory, instruction decoder, controller, etc. is shown.

Further, as an illustration of a sample kernel implementation, the functional diagram of FIG. 5 illustrates a data sequencer 32, a data memory 36, and a configurable arithmetic logic unit (ALU) 34 that can be represented by parameters. 3 illustrates preferred functional elements for implementing kernel 18, including.

FIG. 6 illustrates a dynamic reconfigurable logic (DRL) process 64 and main processor
FIG. 6 is a representative functional diagram showing optional interfaces with associated configuration databases for processing functions external to hardware model 50. Preferably, the DRL process is heterogeneous and reconfigurable and implemented using the present invention. As shown, the hardware interface 54 includes a library 62 and a specified function module 6 including a processor software model 57 having a C program model 56 and an input / output device driver 58.
The processor element 52 associated with 0 and the external DRL process 64 are connected.

In this optional embodiment, one or more single or multi-threaded digital information (eg, signal or data representation), eg, general system design or function definitions, algorithms, electronic signal or data files, etc., is provided. , One or more multi
Such an initial prototype design or function is initially profiled to include a thread representation, and is otherwise specifically a functional cooperation or mimicked real with an external DRL process 64. One or more corresponding fixed, parameterized, programmable or configurable logic in the processor model 50, 57 for time signal interaction;
Units or other equivalent functional signal processing kernels or elements may be functionally used, or implemented, for parallel or effectively profiled for similar processing, or otherwise characterized.

The flow chart of FIG. 7 illustrates another feature of the operating steps of the present invention. First, a user-generated or computer-generated function is defined 70 for a prototype or other system design. Then, one or more mathematical analysis or design performance optimization schemes may be applied 72 to the initial design definition. Then, one or more component algorithms for design definition are provided 74, the representation of such algorithms is thereby provided, preferably in a high-level, register transfer, or behavioral functional format, Coded 76.

The algorithm may be profiled and mapped 78, with one or more correspondingly defined kernels 80, preferably one or more identified design building blocks or primitives 86. To manually and / or for optimized or directed operation or implementation of system design modules, functions, signals, components, or other elements thereof.
Alternatively, it may be automatically, functionally defined, or categorized. Profiling and mapping data is also provided to communication semaphores 84 and scheduling and finite state machine controls and parameters 88. The kernel definition 80 and FSM control parameterization and scheduling 88 then implement the single or multi-threaded elements of the present design, along with the reconfigurable kernel element 82, into the processor architecture, as well as the communication semaphore 84. Applied to. FIG. 8 shows representative software code for a sample design showing the use of a multi-threaded kernel 90.

According to one feature of the invention, the profiling process or the reconfigurable algorithm representing it is temporal, whereby a constant time value or degree of change over time. Including the decision. Examples of temporal applications include the receiver algorithms required in cellular wireless systems and any associated signal processing scheme changes for these algorithms that can utilize the profiling methodology of the present invention. In this example, the processing throughput requirement for one path (eg, receive direction) is
The profiling scheme of the present invention may be implemented in hardware-software, or in any design implementation where it may increase or decrease as processing progresses (eg, from the antenna to the final retrieved data representation). It functions to determine other function partitions.

Further, in such a cellular wireless example, multiple methods may perform similar or equivalent signal processing, but may result in different air interface requirements or effective functions. It is possible that you may not know. Different processing forms or functional elements may occur or operate at different speeds, especially in certain system hardware partitions. Since variable processing speeds may be required, and different modes of operational control may be commanded by support for multiple processing streams, some additional non-temporal and temporal profiling techniques may be used. But with respect to possible operational performance points or capacity of such hardware architectures (eg real-time and non-real-time profiling), optimal functional flexibility.
flexibility). In general, it is contemplated that other examples of applications of the present invention may additionally occur with cellular wireless, including fixed wireless, unauthorized wireless LAN, cordless telephone systems, telemetry, etc. To be

One profiling technique is applied to a hardware-based algorithm for multiple modes of operation to determine the type and number of operations and storage elements required, thereby allowing the designer each time. Functionally different functions can be classified in a form that facilitates identification of commonly used resources.

Other profiling techniques are applied to control multiple levels of hardware definition according to the required frequency of change. Here, mode-dependent changes in the receive path of a wireless receiving device may be, for example, during transaction configuration (eg, where the transaction is a multi-second transaction) and for sub-blocks of data. • Within a second transaction (eg, “on-the-fly”), it may need to change at the start of global reconfiguration.

Depending on the profiling results, the appropriate level of configurable implementation may be selected, eg, for data processing at the highest data rate, which requires control on a cycle-by-cycle basis. However, control may require flexibility and the programmable state machine may provide optimal flexibility to meet the required performance requirements. For data paths that may need to be selected at configuration time but do not change often, programmable interconnects may be applied appropriately.

Furthermore, if the data path selection occurs in real time, the data path-cell
A base multiplexing structure may be applied. Also, for control functions that require an order of operation, a parameterized kernel for processing operations may be applied. Furthermore, for high performance and low flexibility requirements, dedicated datapaths can be applied to optimize silicon implementation. For a multi-standard wireless receiver design, it provides optimal flexibility relative to performance points,
One or more of the profiling techniques described above are applicable.

FIG. 9A illustrates, for example, wired and / or broadcast wireless
One capability, parameter and value configuration table 92 for supplying one or more configuration parameters to a single or multi-threaded reconfigurable system implementation using network download or other send / receive. 1 illustrates the general features of the application of the present invention, including the flow for transferring through an application programming interface (API) according to the above industry or private standards.

Preferred implementations include microprocessors, digital signal processors (DSPs),
Define one or more interconnected block modules 96, which represent an application specific integrated circuit (ASIC), field programmable gate array (FPGA), DRL, or other functional block module, or To implement, it receives configuration parameters through API 94, which may also be defined or implemented in one or more interconnected kernel elements 98. According to one aspect of the invention, one or more configurable parameters 10
0 may be defined or implemented to correspond to one or more identified kernel elements in a threaded manner. Thus, with this configurable parameter, the design and implementation method or system functions to process multi-threaded digital signals or data for improved functional performance.

Generally, system designs or function definitions, algorithms, electronic signals, or data files are provided to include such multi-threaded representations, and initial prototype functions are, for example, time-constrained. May be profiled by one or more threads for concurrency in order to implement the kernel elements represented by certain parameters.

More specifically, in a digital wireless communication application, portable mobile radiotelephone 102 may be connected to other telephones 102 and base stations 104 through digital network 106, as described in FIG. 9B. There is a base station 1
At 04, wirelessly transmit and receive signals. In this network application, the specified design rules, operations, or parameters are
Identifies or supports multithreading for profiling and implementation in programmable kernels or software modules, as well as any symbolic or graphical representations thereof.

Optionally, the kernel element is a base station 104 and / or a telephone unit 10.
May be configured for operation in 2. In particular, the kernel may be a profiled datapath, perhaps according to temporal or non-temporal design constraints.
It may be configured with respect to a sequencer / finite state machine, memory, or other logical structure.

The above-described embodiments of the present invention are provided by way of illustration and description. They are not intended to limit the invention to the precise form described.

In particular, Applicants have found that the functional implementation of the invention described herein is based on hardware,
It is contemplated that software, firmware, and / or other available functional components or building blocks may equally be implemented. Other variations and embodiments are possible in light of the above teachings, and the scope of the invention is limited by the claims rather than the detailed description.

[Brief description of drawings]

FIG. 1 is a diagram of a general methodology and tool architecture for implementation in software and / or hardware that is a preferred embodiment of the present invention.

[FIG. 2A]   FIG. 2A is a functional block diagram for implementing one aspect of the present invention.

FIG. 2B   FIG. 2B is a functional block diagram for implementing one feature of the present invention.

[Figure 3]   FIG. 3 is a representative functional diagram showing the different features of the present invention.

[Figure 4]   FIG. 4 is a representative functional diagram showing the reconfigurable features of the present invention.

[Figure 5]   FIG. 5 is a representative functional diagram showing the features of the kernel of the present invention.

[Figure 6]   FIG. 6 is a representative functional diagram showing the features of the interface of the present invention.

FIG. 7 is a system methodology flow chart illustrating functional operations for implementing one or more features of the present invention.

FIG. 8 depicts a software code stub for implementing one or more features of the present invention.

FIG. 9A   FIG. 9A is a representative functional diagram of one or more applications of the present invention.

FIG. 9B   FIG. 9B is a representative functional diagram of one or more applications of the present invention.

─────────────────────────────────────────────────── ─── Continued front page    (81) Designated countries EP (AT, BE, CH, CY, DE, DK, ES, FI, FR, GB, GR, IE, I T, LU, MC, NL, PT, SE, TR), OA (BF , BJ, CF, CG, CI, CM, GA, GN, GW, ML, MR, NE, SN, TD, TG), AP (GH, G M, KE, LS, MW, MZ, SD, SL, SZ, TZ , UG, ZW), EA (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM), AE, AG, AL, AM, AT, AU, AZ, BA, BB, BG, BR, BY, B Z, CA, CH, CN, CR, CU, CZ, DE, DK , DM, DZ, EE, ES, FI, GB, GD, GE, GH, GM, HR, HU, ID, IL, IN, IS, J P, KE, KG, KP, KR, KZ, LC, LK, LR , LS, LT, LU, LV, MA, MD, MG, MK, MN, MW, MX, MZ, NO, NZ, PL, PT, R O, RU, SD, SE, SG, SI, SK, SL, TJ , TM, TR, TT, TZ, UA, UG, UZ, VN, YU, ZA, ZW (72) Inventor Leeken Keith             United States California             95014 Coupatino La Playa             Coat 21603 F-term (reference) 5B013 DD04 DD10                 5B076 AA02 AA03 DD01 DD04                 5B098 GA05 GC01 GC14 GD01 GD14

Claims (15)

[Claims] 1. A multithreaded computer-aided design system
An automated method for handling system functionality comprising: providing a first function definition representative of a system design; from the first function definition, symbolically representing the first definition. Generating a second function definition, the symbolic representation identifying one or more threads associated with the system design; and each identified by the identified kernel element or set thereof for processing. Profiling the thread. 2. The method further comprising: identifying a common sequence of operations in a thread; and associating the common sequence of operations with a set of operators. The method according to Item 1. 3. The method of claim 2, further comprising the step of associating the set of operators with a sequence of arithmetic operations. 4. The method of claim 2, further comprising the step of associating the set of operators with a sequence of control operations. 5. The method of claim 2, further comprising the step of associating the set of operators with a sequence of memory access operations or locations. 6. The method according to claim 1, characterized in that one or more threads are profiled according to a time function. 7. A device for multi-threaded processing comprising: a first kernel element; and a second kernel element; said first kernel element being by a first thread. Processing a first function represented, the second kernel element processing a second function represented by a second thread, the first thread and the second thread respectively, An apparatus profiled for processing by the first kernel element and the second kernel element, respectively, and wherein the first thread and the second thread are associated with a common function. 8. The apparatus of claim 7, wherein the common sequence of operations is identifiable as a thread and the common sequence of operations is associated with a set of operators. 9. The apparatus of claim 8, wherein the set of operators is associated with a sequence of arithmetic, control, or memory access operations. 10. Apparatus according to claim 7, characterized in that the first or second thread is profiled according to a time constraint. 11. The apparatus of claim 7, wherein the first and second kernel elements are implemented as one or more executable software modules. 12. The first and second kernel elements are implemented as one or more functional modules in a fixed base station or mobile telephone of a wireless communication system. The device according to. 13. A communication system comprising a base station and one or more mobile units, wherein each mobile unit may wirelessly communicate with the base station via a radio signal. A step of generating a first signal representing a system configuration, wherein the first signal symbolically represents one or more function definitions associated with one or more threads in the system configuration. A method for signal processing, comprising: in a mobile unit, profiled for processing by a specified kernel element. 14. A step of receiving the first signal by the mobile unit, wherein one or more kernel elements in the mobile unit comprises:
14. The method of claim 13, further comprising the step of being configured to process one or more threads in the system design according to the first signal. 15. The method of claim 13, wherein one or more threads are profiled according to a time functional constraint.