JP6495208B2 - Method and apparatus for a general purpose multi-core system for implementing stream-based operations - Google Patents

Description

This application claims the benefit of US Provisional Patent Application Ser. No. 61 / 297,139, filed Jan. 21, 2010. The present application is an "Adaptive Integrated Application" filed March 22, 2001, now U.S. Patent No. 6,836,839.
No. 09 / 815,122, now U.S. Patent Nos. 09 / 815,122, entitled "CIRCUITRY WITH HETEROGENEOUS AND RECONFIGURABLE MATRICES OF DIVERSE AND ADAPTIVE COMPUTATIONAL UNITS HAVING FIXED, APPLICATION SPECIFIC COMPUTATIONAL ELEMENTS""HIERARCHICAL INTERCONNECT
U.S. Patent Application Serial No. 10 / 384,486, whose title is the invention, and is now U.S. Patent No. 7,609,297, entitled "HARDWARE." No. 10 / 443,501, entitled "TASK MANAGER". All of these patent applications are incorporated herein by reference.

  The present invention relates generally to programming multi-processor systems, and more particularly to a hardware task manager that effectively exploits the syntax of parallel programming languages that incorporate both streams and threads.

  In general, what limits processing performance in digital systems is the efficiency and speed at which instructions, data, and other information may be transmitted between different components and subsystems within the digital system. For example, the bus transfer rate in a general-purpose von Neumann-type architecture governs the data transfer rate between the processor and memory, resulting in arithmetic performance (eg, million instructions per second (MIPS), floating) A limit will occur in the number of decimal point operations per second (FLOPS: floating-point operations per second, etc.).

  In other types of computer architecture designs, such as multiprocessor designs or parallel processor designs, each of the different processors can communicate with other processors, multiple memory devices, input / output (I / O) ports, etc. In order to achieve this, complex communication capabilities, ie interconnection capabilities, are required. Today, with the complexity of processor system design, the importance of effective and fast interconnects has dramatically increased.

  However, it is difficult to design such a mechanism that optimizes the goals of speed, design flexibility, and simplicity.

At present, parallel programming is performed based on threads as a central and strategic principle of operation. However, threads have significant drawbacks as a computational model. This is because threads are extremely non-deterministic, and rely on programming styles to reduce such non-determinism and achieve critical goals. Testing and verification becomes difficult when this tremendous nondeterminism exists. One solution that has been proposed by GPU (Graphics Processing Unit) vendors is to narrow the form of parallelism that can be represented in a programming model. However, the focus of GPU vendors on data parallelism is to constrain the hands of programmers and prevent them from taking advantage of the full potential of multi-core processors.

  Furthermore, threads are not necessarily executed on banks of the same core. Modern computers (supercomputers, workstations, desktops, and laptops) contain puzzled arrangements of different heterogeneous cores, all of which require separate programming models to program. For example, the motherboard has 1 to 4 main CPUs (central processing unit, eg Pentium processor), each CPU with an on-die or on-package GPU (graphics processing unit, eg NVIDIA's GPU) 1 With six to six on-die CPU cores, the GPU itself has several separate video and audio encoding and decoding cores (multiple video standards such as MPEG2, MPEG4, VC-1, H.264 And 16 to 256 GPU cores, as well as others. Also on the motherboard, 1 to 4 separate high-end, and configurable (meaning that the core can be selected to encode / decode various pre-existing standards) video / audio encoding and There is also a decoding core (multiple video standards such as MPEG2, MPEG4, VC-1, and H.264 with high resolution and multiple audio channels). Additional subsystems of processing cores are added to the motherboard in the form of communication cores (e.g. cores to take over TCP / IP functions. These cores are typically one or more cores. CPU core and one or more packet processing cores: WiFi core, BlueTooth core, WiMax core, 3G core, 4G core) made from one or more broadband / baseband processing cores.

  In modern high-end spectrum devices such as supercomputers, one or four FPGAs (field programmable gate arrays) are added to one motherboard. Each FPGA consists of 100,000 to 10,000,000 very simple CLB processing cores, with multiple hard IP or soft IP CPU cores and multiple DSP cores). Next, these motherboards are themselves copied and interconnected in 100 to 1000 units to make a modern super computer. These systems (desktops / workstations / laptops and / or supercomputers) are then interconnected via the Internet to provide national or global computing capabilities.

  "Managing" and "programming" such a versatile set of cores is extremely difficult. Most programmers do not even try to do this and settle for programming on only one core, ignoring the other cores. In the art, the "embarrassively parallel problems" (e.g., the Google search algorithm has multiple CPUs due to the fact that there is little or no interactivity between parallel threads) There is a fixed number of algorithms known as being easy to distribute between). However, most problems do not have these properties, and a high degree of interactivity and synchronization is required among multiple threads.

Thus, it would be desirable to incorporate multi-threading, unlimited parallelism, and deterministic behavior, as in modern programming language streams. The stream dates back to at least the introduction of the C programming language in 1978, C ++
Have been incorporated into languages such as Java, Visual Basic, and F #. However, in these languages, streams are left with rather narrow roles, such as a framework for I / O and file access. Therefore, it is desirable to extend the role of streams in parallel programming to a class that is roughly comparable to the class of objects, ie, the class of variables.

  According to one example, a programmable core based computing device is disclosed. The computing device comprises a plurality of processing cores connected to one another. The memory stores stream domain code including a stream that defines a stream destination module and a stream source module. The stream source module assigns data values to the stream, and the stream communicates data values from the stream source module to the stream destination module. The runtime system detects when data values are available to the stream destination module and schedules the stream destination module to be run on one of a plurality of processing cores.

  Additional aspects of the present invention will be apparent to those skilled in the art in view of the detailed description of various embodiments made with reference to the drawings. A brief description of the drawings is provided below.

FIG. 7 is a schematic diagram of an adaptive arithmetic engine compatible with the disclosed stream-based programming model. FIG. 2 is a block diagram of an adaptive computing machine compatible with a programming model. FIG. 3 is a diagram showing a network word in the network of adaptive computing machines shown in FIG. 2; FIG. 3 illustrates a node wrapper interface between foreign nodes and a homogeneous network in the ACE architecture of FIG. 1 or the ACM architecture of FIG. 2; FIG. 5 illustrates the basic components of the hardware task manager used for the node wrapper in FIG. 4; FIG. 3 illustrates point-to-point channels used to stream data in the ACM architecture shown in FIG. 2; FIG. 7 is a diagram illustrating a point to point network word used by the point to point channel in FIG. 6; FIG. 6 shows modules for nodes for different stream flows. FIG. 6 shows modules for nodes for different stream flows. FIG. 6 shows modules for nodes for different stream flows. FIG. 6 shows modules for nodes for different stream flows. FIG. 7 is a diagram illustrating substitution of values into streams. FIG. 7 is a diagram illustrating substitution of values into streams. FIG. 5 illustrates a 5-tap FIR filter that may be modeled using modular and stream concepts. FIG. 6 shows a module with FIFOs of different configurations. FIG. 6 shows a module with FIFOs of different configurations. FIG. 6 shows a module with FIFOs of different configurations. FIG. 7 is a flowchart of a thread used in the programming language example. FIG. 2 illustrates a form of a combined operation of the example programming language. FIG. 2 illustrates a form of a combined operation of the example programming language.

  Adaptive arithmetic engine and adaptive arithmetic machine

  FIG. 1 is a block diagram showing an example of a multiprocessor system using one operation model example. Apparatus 100, referred to herein as adaptive arithmetic engine (ACE) 100, is preferably embodied as an integrated circuit or as part of an integrated circuit with other additional components. In the exemplary embodiment, and as discussed in more detail below, the ACE 100 may be configured to communicate with one another with one or more reconfigurable matrices (or nodes) 150, such as the illustrated matrix 150A-matrix 150N. And a connection network 110. In the exemplary embodiment, and as discussed in more detail below, one or more matrices 150, such as matrix 150A and matrix 150B, are configured to function as controller 120, while matrix 150C and matrix 150D. , Etc. are configured to function as memory 140. The various matrices 150 and the matrix interconnect network 110 may be implemented together as fractal subunits, which may be on the order of a few to a thousand nodes.

  In the preferred embodiment, ACE 100 is for signaling and other transmissions between reconfigurable matrix 150, controller 120, and memory 140, or for other input / output ("I / O") functions. It does not utilize conventional (typical separate) data, DMA, random access, configuration, and instruction buses. Rather, data, control, and configuration information is transmitted between these matrices 150 utilizing matrix interconnection network 110. Note that this matrix interconnection network 110 is configured and reconfigured in real time to provide any given connection between the reconfigurable matrix 150 including the controller 120 and these matrices 150 configured as the memory 140. Is possible.

  Matrix 150 configured to function as memory 140 may be implemented in ACE 100 in any desired or exemplary manner utilizing computing elements (described below) of fixed memory elements. Or may be incorporated within another IC or within a portion of an IC. In the exemplary embodiment, memory 140 is contained within ACE 100 and may preferably be comprised of computing elements that are low power consuming random access memory (RAM), but may be flash, DRAM, SRAM It may be composed of computing elements of any other form of memory such as MRAM, ROM, EPROM, or E2PROM. In the exemplary embodiment, memory 140 preferably includes a direct memory access (DMA) engine, not specifically shown.

The controller 120 is preferably an adaptive finite state machine (FSM), a reduced instruction set ("RISC") processor, a controller having the ability to perform the two types of functions described below. Or, it is implemented using the matrix 150A and the matrix 150B set as another device or IC. Alternatively, these functions are conventional RS
It may be implemented using C or another processor. The first control function, referred to as "kernel" control, is illustrated as a kernel controller ("KARC") of matrix 150A, and the second control function, referred to as "matrix" control, is a matrix controller ("MARC") of matrix 150B. ")). The control functions of the controller 120 kernel and matrix refer to the configurability and reconfigurability of the various matrices 150, and combined data, settings, referred to herein as "silverware" modules, And will be described in detail below with reference to exemplary forms of control information.

  The matrix interconnect network 110 of FIG. 1 comprises a subset interconnect network (not shown). These interconnection networks may be Boolean interconnection networks, data interconnection networks, and collectively and generally herein "interconnect", "interconnection (s)", " An FPGA interconnection network or switching fabric, as is commonly known in the art, including other networks or interconnection schemes referred to as "interconnection network (s)" or "networks" It can be implemented in various ways, such as using. In an exemplary embodiment, the various interconnect networks may be configured, for example, as in US Pat. No. 5,218,240, US Pat. No. 5,336,950, US Pat. No. 5,245,227, and US Pat. , As described in U.S. Pat. These various interconnection networks provide selectable (switchable) connections between controller 120, memory 140, various matrices 150, computing units (or "nodes"), and computing elements, thereby A physical basis is provided for performing the configuration and reconfiguration described herein in response to or under the control of configuration signals generally referred to herein as "configuration information." In addition, the various interconnect networks (110, 210, 240 and 220) can be used to replace the controller 120 in place of any form of conventional or separate input / output bus, data bus, DMA, RAM, configuration and instruction bus. , Memory 140, various matrices 150, and selectable, switchable data, input, output, control, and setup paths among computing units, components, and elements.

  However, although switching or selection operations of various interconnection networks or within various interconnection networks may be implemented in a manner well known in the art, the design and layout of the interconnection network according to the present invention are as follows. It should be pointed out that it is new and new as described in detail in. For example, different levels of interconnection are provided corresponding to different levels of matrices, computing units, and elements. At the level of matrix 150, matrix interconnect network 110 with lower connectivity in a given area compared to prior art FPGA interconnects is more restricted and has a lower "richness", so that capacitance Is reduced and the operating speed is increased. However, within a particular matrix or computing unit, the interconnect network may have higher adaptation and reconfigurability capabilities in narrow or close reference locality because it is significantly denser and richer .

The various matrices or nodes 150 are reconfigurable and disparate. That is, generally, depending on the desired settings, reconfigurable matrix 150A is generally different from reconfigurable matrix 150B to matrix 150N, and reconfigurable matrix 150B is generally configured to be reconfigurable matrix 150A. And unlike matrix 150C to matrix 150N, resettable matrix 150C generally differs from resettable matrix 150A, matrix 150B, matrix 150D to matrix 150N, and so on. The various reconfigurable matrices 150 generally each contain different or various mixed, adaptive and reconfigurable nodes or computing units, and then the nodes are generally different or mixed, It can be adaptively connected, configured and reconfigured in various ways, including fixed, application specific computing components and elements that perform different functions through different interconnection networks. In addition to the various internal settings and reconfigurations, the various matrices 150 can be connected, configured, and reconfigured at a high level to each of the other matrices 150 through the matrix interconnection network 110. Details of the ACE architecture can be found in the related patent applications referenced above.

  Another example of an adaptive computing machine 160 that may use a parallel computing model is shown in FIG. The adaptive computing machine 160 in this example has 32 heterogeneous leaf nodes 180 connected together via a network 162. The network 162 has a group of network input ports 164, a group of network output ports 168, an optional system interface port 170, an external memory interface 172, and a single route 164 connected to an internal memory interface 174. Supervisor node or K node 178 is also connected to route 164.

  Nodes 180 are each grouped into quaternary trees, such as quaternary tree 182. Quaternary trees, such as quaternary tree 182, are implemented using 5-port switch elements 184, each connected to a single parent node and up to four child nodes 180. This switch element implements a fair round robin arbitration scheme and provides a pipeline with multi-level lookahead for performance enhancement. In this example, the width of the entire path is constant (51 bits), but in the style of Faters tree in Leiserson, an option is available to extend the path as the tree climbs, to increase the bandwidth of the network It is.

In this example, all traffic on network 162 is in the form of a 51-bit network word, as shown in network word 188 of FIG. Network word 188 includes route field 190, security bits 192, service field 194, auxiliary field 196, and payload field 198. The route field 190 is the destination address of the network word 188. The upper two bits in the route field 190 are chip IDs. Security bit 192 allows for peak (read) and poke (write) to configuration memory. Security bit 192 is set only for the word sent by K-node 178. The service field 194 defines the service type and the auxiliary field 196 depends on the service type. The service field 194 defines one of sixteen service types, including point-to-point (PTP). Note that this PTP relates to streaming data and PTP acknowledgment, and PTP acknowledgment supports flow control for data, and increments or decrements the consumer count or producer count at the destination node.
Node wrapper

  FIG. 4 illustrates the interface between foreign nodes and a homogeneous network in the ACE architecture of FIG. 1 or the ACM architecture of FIG. This interface is referred to as a "node wrapper" because it is used to provide a common input and output mechanism for each node. The execution units and memories of nodes are connected to the network and control software via node wrappers, thereby providing a uniform and consistent system level programming model. In this example, node 180 comprises memory 210 and execution unit 212. Details of the node wrapper can be found in the related patent application referenced above.

  In the preferred embodiment, each node wrapper comprises a hardware task manager (HTM) 200. The node wrapper also comprises a data distributor 202, an optional direct memory access (DMA) engine 204, and a data aggregator 206. The HTM coordinates the execution or use of node processors and resources, respectively. The HTM does this by processing the task list and creating a ready to run queue. The HTM is configured and managed by a dedicated or control node (not shown), referred to as K node 178 in FIG. However, other HTM control techniques may also be used.

  The node wrapper in FIG. 4 makes node 180 equal in appearance to all other nodes of adaptive computing machine 160 in FIG. 2 or adaptive computing engine 100 in FIG. 1 regardless of its internal structure or function. . The node wrapper also frees execution unit 212 from having to handle countless activities related to task management and network interaction. Among other things, the node wrapper is responsible for processing each of the received network words, such as network word 188 of FIG. 2, in a proper manner within one clock cycle.

  The execution unit 212 in FIG. 4 is in charge of the task execution function (the task is equivalent to a module instance). Execution unit 212 may be a digital signal processor (DSP), a reduced instruction set (RISC) processor, a domain-specific processor, an application-specific integrated circuit (ASIC), or a reconfigurable (FPGA) It may include a fabric. Regardless of its form, execution unit 212 interacts with the node wrapper through a standard interface.

  Node memory 210 is accessible to both node wrapper and execution unit 212. The node memory 210 is at a position where the node wrapper stores streaming data to be received and the execution unit 212 accesses the data. The node's own memory 210 is typically not at a position where the execution unit 212 sends output data. In order to minimize memory accesses, output data is usually sent directly to the requesting node, ie the consuming node (s). The node memory 210 is also used to store task parameters, and is available to tasks as a temporary (working) storage area.

  In a multi-node system such as the ACM 160 of FIG. 2 in which the node 180 is a consumer and a producer of streaming data, it is desirable that the production speed and the consumption speed match. The creator task on one node may create data at a higher or lower rate than consumer tasks on other nodes can handle it. If the producer sends data at a higher rate than the consumer can handle, the data will be lost eventually. If the producer sends data at a lower rate than the consumer can handle it, the consumer becomes starved of the data, so that the consumer is wasted waiting for additional data Can be forced.

ACM 160 provides a uniform and consistent mechanism for task management, flow control, and load distribution via point-to-point protocol and the node wrapper of FIG. Task management ensures that the task is in the running state only if the task has sufficient input data and there is enough space to accommodate the data generated by the task at the consuming node (s). It becomes a thing. Flow control ensures that the creating task does not overwhelm the consuming task with too much data in too short a time. Load balancing allows the creating task to distribute data among several alternative consuming nodes, so that the creating task can operate at higher speeds.

  Streaming data is transferred between nodes 180 (point) via a point-to-point channel (point-to-point stream) 250 shown in FIG. Each PTP channel, such as a point-to-point channel, includes a producer node 252, a producer task 254, an output port 256, a consumer node 258, an input port 260, an input buffer 262, and a consumer task 264. The creator task 254 is executed on the execution unit of the creator node 252, and produces PTP data of a finite size block for each task activation. Blocks of data are transmitted on PTP channel 250 as a series of PTP words. The transmission of blocks is shown as a task in FIG. The output port 256 on the creating node 252 is associated with the creating task 254.

  Consumer task 264 receives PTP data from PTP channel 252 via an input port on consumer node 258. The circular input buffer 262 in the node memory of the consumer node 258 stores the received PTP data. A consumer task such as the consumer task 264 is executed on the execution unit of the consumer node 258 for each activation of the task (task 2 in FIG. 5), and a limited amount of PTP data exists in the circular input buffer 262. To consume

  Data is conveyed on PTP channel 252 as producer task 254 transmits the 50 bit point to point word 270 shown in FIG. 6 to the node wrapper of producer node 252. The point-to-point word 270 has the same fields as the network word 188 of FIG. 3 and the same elements / fields are given the same element numbers as the element numbers of FIG. Point-to-point word 270 includes node word 272 in root field 190, port word 274 in auxiliary field 196, and data word 276 in payload field 198. In this example, the 51st bit, the security bit 192, is added back by the network 162 of FIG. A node wrapper, such as the node wrapper of FIG. 4, then passes the PTP word to the packet switched network for transmission to the consuming node 258 in FIG. The 8-bit root field 190 of the PTP word 270 provides the address in the form of a node word 272 of the consuming node, such as node 258 in FIG. Port word 274 includes the lower five bits of auxiliary field 196 which indicate which input port of the consumer node's input port the data is destined for. When the PTP word reaches the consuming node, the node wrapper stores the 32-bit data word 176 in the payload field 198 in a circular input buffer associated with the indicated input port. Thus, transmission is completed.

  ACM 160 provides mechanisms for task management, flow control, and load balancing. There is an input buffer associated with each input port. There are also two's complement signed counts associated with both input and output ports.

  For the input port, the count is referred to as the consumer count. Because this count reflects the amount of data in the port's input buffer that is available to be consumed by the associated task. The consumer count is validated if its value is non-negative, ie if its sign bit is zero. The enabled consumer count indicates that the associated input buffer has the minimum amount of data required by activation of the associated task. At system initialization or reset, the consumer count is typically reset to -C. C is the minimum number of 32-bit words required for each task activation.

  For output ports, the count is referred to as the producer count. Because this count reflects the amount of space available in the downstream input buffer to accept data created by the associated task. The producer count is validated if its value is negative, ie if its sign bit is one. The enabled creator count indicates that the downstream associated input buffer has space available to accommodate the maximum amount of data created per activation of the associated task. At system initialization or reset time, the producer count is typically reset to P-S-1. Here, P is the maximum number of 32-bit words created for each task activation, and S is the size of the downstream input buffer in the 32-bit words.

  Both consumer count and producer count are typically initialized to a negative value so that consumer count is in an invalid state at the start, while producer count is in a valid state at the start is there. This initial state reflects the fact that the input buffer is normally free at system initialization / reconfiguration.

  Consumer counts and producer counts are updated by the debit system in the form of forward acknowledgment and backward acknowledgment. Both types of acknowledgments are network words, such as the acknowledgment network word 280 shown in FIG. The acknowledgment network word 280 has the same fields as the network word 188 of FIG. 3 and the same elements / fields have the same element number. An acknowledgment network 280 words are sent by the task as the final step of task activation. In both cases, the payload field 198 has four sub-fields: an acknowledgment type sub-field 282 (1 bit), a port sub-field 284, (3) task sub-field 286, and an Ack value sub-field 288. .

  A series of acknowledgments that the task performs at the end of each activation are described below. For each output port of the task, a forward acknowledgment specifying the consumer input port and the consumer task is sent to the consumer node. The Ack value is the number of PTP words that the task has sent to the consuming input port. The backward acknowledgment (self ack) specifying the output port and task is sent to the node where the task resides. The Ack value is the number of PTP words that the task has transmitted via the output port.

For each input port of the task, a backward acknowledgment specifying the creator output port and the creator task is sent to the creator node. The Ack value is a value obtained by adding a minus sign to the number of 32-bit words that the task has consumed from the buffer of the input port. Forward acknowledgment (self ack) indicating the input port and task is sent to the node where the task resides. The Ack value is a value obtained by adding a minus sign to the number of 32-bit words consumed by the task from the buffer of the input port.
Hardware task manager

  The hardware task manager 200 shown in FIG. 4 is part of a node wrapper that is responsible for updating consumer and creator counts in response to an acknowledgment being received. The hardware task manager 200 also monitors the sign bit of these counts and launches tasks when the appropriate set of counts is enabled. This last task is satisfied using two signed counts associated with the task rather than the port: task input count and task output count. The task's input (output) count reflects the number of activated task consuming side (creation side) counts. The task count is enabled if its value is non-negative. A task is enabled and available for execution when both its input count and output count are enabled.

  Acknowledgments that receive update the various counts so that the task is triggered as follows. When forward acknowledgment is received, the designated port is interpreted as an input port and an Ack value is added to the corresponding consumer count. When the consumer count transitions from the inactive state to the active state (from the active state to the inactive state), the input count of the designated task is incremented (decremented) by one. When a backward acknowledgment is received, the designated port is interpreted as an output port and an Ack value is added to the corresponding creator count. When the creator count transitions from the invalid state to the valid state (from the valid state to the invalid state), the output count of the designated task is incremented (decremented) by one. If a backward acknowledgment or forward acknowledgment is received and both the input count and output count of the specified task are enabled, then the task is on the ready to run queue if it is not on the ready to run queue Will be put. The task is launched when it reaches the top of the queue.

These actions embody start-up rules for the task. As a result, the task is placed in the execution ready queue, and the task is executed when a sufficient number of consumer counts and a sufficient number of creator counts are finally activated. These sufficient numbers of concrete values are determined by the initial values of the task's input count and output count. I (O) is the number of input (output) ports associated with the task, IC _Initial (OC _Initial ) is the initial value of the task's input (output) count, and all consumption as described above Assuming that the side count is initially in an invalid state and all the creator counts are initially in a valid state, the task is:
Of the I consumer counts, _{-IC Initiail} is in active state,
If (O-OC _Initial ) out of the O producer counts are in the valid state, start up.
For example, for I = 4
If IC _Initial = -1, then one of the four consumer counts must be enabled.
If IC _Initial = -2, then two of the four consumer counts must be validated.
If IC _Initial = -3, 3 out of 4 consumer counts must be enabled.
If IC _Initial = -4, then 4 of the 4 consumer counts must be enabled.
For O = 4,
If OC _Initial = 3, then one of the four creator counts must be enabled.
If OC _Initial = 2, then two of the four producer counts must be enabled.
If OC _Initial = 1, then three of the four producer counts must be enabled.
If OC _Initial = 0, then 4 of the 4 creator counts must be enabled.

Programming of a multiprocessor system such as ACE 100 in FIG. 1 and ACM 200 in FIG. 2 may be done using what may be referred to as the Stream C programming language.
Stream C module

  In a stream C program, there is only one mechanism to express parallelism. The mechanism is to use the parallel operation of modules (and stream expressions like modules) of a program. Syntactically, modules are very similar to C functions, but semantically they are different from modules and functions. The C function (subroutine) starts its operation only when it is called. When called, control is passed to the C function, usually with input arguments. The C function then performs the task / operation and, upon completion, returns control with the output result. Unlike C functions, modules are never called, and control is neither passed to nor returned from modules. Instead, the modules perform ongoing interactions with other modules and the outside world through input and output ports. Through these ports, the module receives a stream of input values and issues a stream of output values.

  The syntax of module prototypes is the same as that of C function prototypes, with three exceptions. First, the keyword stream precedes the module prototype. This keyword tells the compiler / linker that each module input and module output is associated with a stream of values of the specified type, not with individual values. Second, to allow the module to have multiple main stream, the module's return type can be replaced by a parenthesized list that is identical in syntax to the input parameter list. Third, in order to extend the concept of arrays into modules, a bracketed list of array indices may be inserted immediately after the module name and just before the input argument list. The module arrangement is discussed below.

The following formula,
stream int moduleA (int, int);
stream (int, int) moduleB (int, int);
Are two examples of module declarations. Parameter names are omitted here. Because parameter names are not required in module declarations (as opposed to module definition or module instantiation). However, parameter names may also be included at the programmer's discretion, usually as an aid to storage, to the input, and also to the output if there are multiple outputs. For example, two declarations can be expressed as:
stream int moduleA (int a, int b);
stream (int x, int y) moduleB (int a, int b);

  The first declaration indicates that moduleA has two input streams, both of which are of integer type, and that it has a single output stream, which is also of integer type. The second declaration indicates that moduleB has two input streams, both of which are of integer type, and which have two output streams, which are also of integer type.

Similar to the C function definition, the module definition has a body enclosed in braces ({and}). As with the C function definition, each module input (and each output module if there is more than one output) is assigned an identifier. The following are two examples of module definition.
stream int moduleA (int a, int, b)
{
/// main body of module
}

stream (int x, int y) moduleB (int a, int b)
{
/// main body of module
}

Module instantiation is the counterpart in modules to C function calls. Like function calls, module instantiation is where modules are used. The syntax of these two types of expressions is similar but the semantics are different. One part of the C code can be expressed as follows.
int x, y;
int F (int, int);
.
.
.
int z = F (4, x + 5 * y);

  The first statement declares that x and y are positive numbers, while the second statement declares that F is a function with two integer parameters and one integer result. The last statement is an assignment statement containing the function call F (4, x + 5 * y), where the function F (4, x + 5 * y) corresponds to the two parameters, namely the two parameters of F, Equation 4 and It has the formula x + 5 * y.

The streamed version of this partial code is as follows:
stream int x, y;
stream int F (int, int);
.
.
.
stream int z = F (4, x + 5 * y);

  In this stream version, in each of these statements, the keyword stream is at the top. Because of the change in syntax, there is also a dramatic change in semantics. Instead of individual values, a stream of values is used. Thus, the first statement declares that x and y are integer streams, while the second statement declares that F is a module with two integer stream inputs and integer stream outputs. The last statement is an assignment statement that includes module instantiation F (4, x + 5 * y). This F (4, x + 5 * y) has stream expression 4 and stream expression x + 5 * y, corresponding to two arguments, namely two parameters of F.

In the case of a function call, whenever substitution z = F (4, x + 5 * y) is executed, expressions 4 and 4, x + 5 * y are evaluated, and the resulting two values are used as parameters to call function F Supplied to After a certain time, F returns a value. In the case of module instantiation, the assignment statement z = F (4, x + 5 * y) is not executed, and the function F is not called. Instead, at system initialization, just before the stream C program starts execution, an instance of the function F is instantiated, whereby the instance receives an integer stream on its two input ports, And is ready to create an integer stream on its output port. When program execution is started, an instance of F retains its operating state (ie, an instance of F is permanent) until the end of the program.

  This simple example shows the general mechanism used to create a collection of interacting modules in stream C. With each module instantiation, a separate module instance is created at system initialization. Once instantiated, the module instance is ready to receive a stream of values on its input port and to create a stream of values on its output port. Furthermore, when program execution is started, the module instance holds the operating state until the program end time.

The general form of instantiation of a module with multiple output ports is as follows.
(<Identifier list>) <module identifier>(<expressionlist>)
Output arguments are identifiers, while input arguments are expressions. These identifiers serve to provide a name for the unnamed output stream. The above stream assignment statement plays the same role by assigning the name z to the output stream without the name F (4, x + 5 * y). For example,
stream int w, x, y, z;
stream (int, int) F (int, int);
.
.
.
(W, z) = F (4, x + 5 * y);

As mentioned above, F has two integer stream inputs, but in contrast to the previous example, this F has two integer stream outputs. These two output streams have identifiers (w,
Appears upon instantiation of F as a list of z). Note that this works to give the two output streams the names w and z.

  The statements inside the module body allow you to read threads from the stream and write threads to the stream besides stream statements involving only the stream, including the full range of C statements Are classified as thread statements that contain In stream C, a module has its own instantiation within its body, or within the body of a submodule, as a separate module instance is created at system initialization by the instantiation of each module I can not do it. In other words, the cyclicity of the module reference is not possible. This prohibition helps to avoid the difficult task of instantiating an infinite number of module instances.

There is no notion of returning control in the stream C module, so the return statement is not suitable. In modules, output values are simply inserted into the module's output stream. However, to do that, the output stream must have a name. That is not a problem for modules that have a list of output streams with names in parentheses. However, it is a problem if the module prototype only provides the type of output stream of the module. In that case, the code within the body of the module can use the keyword out as the name of the default module output stream, either in the stream domain or in the thread domain. This usage is illustrated in the partial code below.
stream int moduleA (int a, int b)
{
.
.
.
out = a + b;
.
.
.

  The functions provide the operation building blocks of the program, whereas the modules, and the streams associated with the modules, provide a framework for interaction networks and parallel operations typical of stream C programs. A module processes a stream of values, which does not make it impossible for the module to access the individual values in the stream and to provide these values to the function. Similarly, the module can access the output value of the function and insert that value into the stream. On the other hand, functions can not refer to modules. This is because there is no mechanism for such interaction in the function. This asymmetry in capability shows that the module is at a higher level while the function is at a lower level on the program hierarchy.

  While the differences between modules and functions are substantial, there is one domain where modules and functions are similar. That is, both modules and functions support side effects. That is, both modules and functions can manipulate external data structures independently of their respective input and output ports. This stems from the fact that a module may contain threads that may have side effects.

  FIG. 8A shows module 300, several (zero to N) input streams 302 that provide data / control to module 300, and some that provide data / control to the next module / function. A general module is shown, including (zero to N) output streams 304. Modules that do not have an output stream are "sinks" and streams that do not have an input stream are "sources."

  FIG. 8B is a diagram showing two modules, namely module A 300 and module B 310, each module having input streams 302 and 312 and output streams 304 and 314. The output stream 304 of module A 300 is connected to the input stream 312 of module B 310. The module A 300 is mapped to execute on the CPU core 308, and the module B 310 is mapped to execute on the second CPU core 318. Cores 308, 318, and 328 are similar to node 180 of FIG.

FIG. 8C is a diagram illustrating mapping of the module A 300 and the module B 310 to the same CPU core such as the CPU core 308. In this case, modules 300 and 310 behave like any other separate control thread. The operating system running on the second core 318 may schedule the modules 300 and 310 based on preemptive multitasking or run to completion / release. Both modules 300 and 310 and input / output streams 302, 312 and 304, 314 are "permanent" (ie, they remain ready for processing execution), so "enough" to perform the operation. Additional information on when to schedule modules based on both the availability of input stream data and of the "sufficient" space where the output stream can carry computed data can be obtained from the conventional operating system. Must be provided to the system.

  A variety of different algorithms can be used to perform the module to core mapping. These algorithms may include cache neighborhoods. Note that in the cache neighborhood, the modules sharing the largest number of streams are to the core sharing the L1 cache following the shared L2 cache following the shared L3 cache following the shared DRAM Will be put. These algorithms may also include physical neighborhood algorithms. In the physical neighborhood algorithm, modules sharing the maximum number of streams are placed in cores physically close to each other. For example, the algorithm may start at the die and then move to integrated circuits on the motherboard, then to the motherboard on the rack, then to the rack on the same floor of the building, and then to the geographically close building. Another algorithm may be the next available free. Note that the modules are cored based on the CPU utilization (current utilization or weighted average utilization over time) or the next "free" core, which in turn is based on the next available core. Assigned to Another algorithm may be the expected load. Note that this selects modules and cores based on the estimated statistical sampling. A running average of core utilization may be used to load the module onto the lightest core. Another algorithm is user specified. Here, the virtual core ID specified by the user is used to place all modules on the physical core ID. When the number of virtual core IDs exceeds physically available cores, multiple modules are loaded evenly across the available physical cores.

FIG. 8D shows various data structures 330, 332, and 334 that may be present in module A 300 and used in input stream 302 and output stream 304. Data structures 330, 332, and 334, which may reside in either a memory / cache or TLB, allow single-core or multi-core systems to transport data from an input stream such as input stream 302 to an output stream such as output stream 304. And transports the input stream 302 to a module such as module A 300, and contains the important information needed to schedule the input of module A 300 to the output stream 304. For each module, uniquely identify that module, uniquely identify all input streams for that module, uniquely identify all output streams for that module, and "connect" the input and output streams The information exists that uniquely identifies the core, identifies the cores, and holds state information such that modules are relocated from one core to another, ie, swapped out through virtual memory. Streams can be dynamically added or deleted from modules, and modules can be dynamically added or deleted from cores.
stream

  Stream The term stream in the C programming language refers to a series of data values that are all of the same data type and are typically available for a period of time. However, in stream C, the stream provides functionality far beyond the framework for input and output. The stream is enhanced to a position that is roughly comparable to that of the first class of objects, ie, variables. This means that the stream can be combined with the identifier (ie, the stream can be given a name), that it can be combined with the input parameter of the function (ie input parameter of the module), the output of the function (ie input parameter of the module) Means that it can be combined with the parameters in the formula, and can be combined with the output of the formula.

A stream conveys values of a single data type from one or more stream sources to one or more stream destinations. The exact details of how this transport is accomplished depends on the implementation, and in particular whether the stream is limited to a single semiconductor die, or whether the stream spans a few meters or even thousands of kilometers It depends on you. Unless dealing with performance issues, programmers do not need to consider these details, only the four stream attributes: stream type, stream name, stream source, and stream destination. It should be taken into consideration.

  The stream type indicates the type of value being conveyed. Stream types that may be legal data types of C, including data types defined by pointers and typedefs, may be implicitly specified by context, for example by appearing as module input or output parameters, or described below It can be explicitly specified using the stream declaration.

  The stream source is where the values are placed in the stream. Possible stream sources include module defined input parameters, module instantiation outputs, stream expressions output, and threads (described below). The stream destination is the position at which the stream conveys its value to that point. Possible stream destinations include module defined output parameters, module instantiation input arguments, stream expression inputs, and threads. An optional stream name is a name / identifier assigned to a stream when the stream appears as module input or module output, or when the stream is introduced in a stream declaration. One example of a stream without a name is a streamed output stream that has no name assigned by stream assignment.

The notion of stream attributes is illustrated by the following partial code, including the declaration of function F and the partial definition of module M:
stream int F (int, int);
stream (int zStrm) M (int xStrm, int yStrm)
{
・
・
・
zStrm = xStrm * yStrm + F (xStrm, yStrm);
・
・
・
}

  Here, there are three streams with names: xStrm, yStrm and zStrm, all of which are data types of int. xStrm and yStrm each have a single source which is an input parameter of module M. The destinations of xStrm and yStrm are represented by two instances of xStrm and yStrm, which appear in substitution expressions in the body of M, (remember, in C, substitution is also an expression). These instances represent inputs to assignment expressions. Thus, xStrm and yStrm each have a single source and two destinations.

The stream expression is the same as the C expression except that in the stream expression there is an input stream instead of a variable. The stream expression also has an output stream, which conveys the results from the expression evaluation. By default, the output stream does not have a name, but it is possible to assign a name by using stream substitution just as you did in the above substitution. Therefore, the stream expression xStrm * yStrm + F (xStrm, yStrm)
The output stream of is stream assignment zStrm = xStrm * yStrm + F (xStrm, yStrm)
Assigns the name zStrm. Either of these two formulas can be considered to be the source of zStrm. The destination of zStrm is the output stream of module M indicated by the output parameter zStrm of module M.
stream (int zStrm) M (int xStrm, int yStrm)
Thus, xStrm has a single source and a single destination.

  The most important attribute of the stream relates to the role that the stream plays in conveying the value. There are four such attributes. That is, a) the value does not enter the stream except at the stream source or at system initialization using the initialize () function, b) the value entering the stream at a single source is completely ordered in time (C) once in the stream, the values are delivered to all stream destinations eventually, and if there are multiple destinations, separate copies of the values are delivered to each destination, and d The values from the single source are received at each stream destination in the same order as the values entered the stream (ie there is no jump in values in the stream). These four attributes are the only guarantees that the stream provides for the transport of values. Any other attribute that does not follow as a logical outcome from these four attributes is not a general stream attribute.

  The stream is obligated only to deliver the value ultimately. Thus, the latency of the stream, ie the time it takes for the value to move from the stream source to the stream destination, is indeterminate. In fact, latency can vary with time, or between source-destination pairs of the same stream. However, constant or at least bounded latency can be achieved by relying on the guarantees provided by the system implementation (rather than the programming model). For example, source-destination pairs limited to a single semiconductor die usually have limited latency.

Also, the four attributes mentioned above imply the determinacy and non-determinacy (uncertainty) of the stream. For streams with a single source, four attributes ensure deterministic stream behavior. That means that the order in which the values are placed in a single source stream completely determines the order in which the values are delivered to all stream destinations. However, in the case of a stream with multiple sources, the situation is very different. To illustrate the problem arising from multiple stream sources, consider the following application of the following partial code continuing to the previous section (out is the default output stream of a single output module):
int F (int);
stream int M (int xStrm, int xStrm)
{
・
・
・
out = xStrm * xStrm + F (xStrm);
・
・
・
}

  The two input parameters of module M are identical xStrm. From the four attributes, the values entered into xStrm through the first input parameter of module M will be received at each of the three destinations of xStrm in the same order as these values entered the stream. The values entered into xStrm through the second input parameter of module M will be received in each of the three destinations of xStrm in the same order as these values entered the stream. This means that the values of the two streams are merged or interleaved before reaching the respective destinations of xStrm.

  How the interleaving is performed is generally influenced by the configuration of the program. For example, the missing part of the above program may be configured to be correctly interleaved between the values of parameter 1 and parameter 2. For example, the integers arriving at the two input parameters (stream) xStrm of module M have the following order:

If we have the formula out = xStrm * xStrm + F (xStrm)
The order of arrival at each of the three xStrm destinations is

It can be in the form of However, the determinacy imposed by the program does not always hold in this way, and values from multiple stream sources may be interleaved non-deterministically. Furthermore, depending on the target system, these non-deterministic alternations may differ from one stream destination to another. Thus, for example, if the values reached on the two input parameters (streams) of module M are the same as in the above case, the order of arriving at the three destinations of xStrm is

It can start in the form of The nondeterminism of arrival order at multiple source stream destinations is in contrast to the consistency of arrival order across all destinations of a single source stream. If the arrival order is fixed, it is possible to apply the following useful notation: For a single source stream ssStrm and a non-negative integer i
ssStrm (i)
Indicates the ith value that appears in all destinations in ssStrm. By convention, ssStrm (0) denotes the first value appearing at all destinations.

  When the value reaches the stream destination, if the destination is a module definition or module instantiation input argument, the value is passed to the stream on the other side of the module boundary. Thus, the value remains in transition. If the destination is a streamed input or thread, the value is placed in the FIFO queue.

The following partial code is shown to indicate staying in transition:
stream int module1 (int);
stream int module2 (int xStrm)
{
・
・
・
out = modulel1 (xStrm);
・
・
・
}
This partial code contains two modules, namely module1 and module2, each of these two modules having a single input stream and a single output stream, and streams xStrm and yStrm with two names (both and exists in the definition (body) of module2. The only destination of xStrm, module1 (xStrm), is an input argument for instantiation of module1. The value reaching this destination simply passes the boundary of module 1 and reaches the internal stream of module 1. This situation is the only destination stream of yStrm (int yStrm) module2 (int xStrm)
The same is true for the values reaching. Because this destination is an output parameter of module 2, the arriving value simply passes the boundary of module 2 and reaches the stream outside of module 2.

Another example is where the stream destination is a streamed input, such as the following partial code:
stream int F (int, int);
stream int M (int xStrm, int yStrm)
{
・
・
・
out = xStrm * yStrm + F (xStrm, yStrm);
・
・
・
}
Stream expression xStrm * yStrm + F (xStrm, yStrm)
Is in the body of module M, this stream expression contains two destinations of xStrm and two destinations of yStrm. This stream expression includes two operators * and + and a function F, which are normal C syntax. This means that two operators and the function F should be supplied with individual values in order to evaluate this expression.

  The queue is automatically inserted by the stream C linker / loader and managed by the stream C runtime. Some of the runtime's mission is to signal when queues are free and to ensure that no queues overflow. The programmer may request a specific amount with pragma commands as described below, but each queue is guaranteed to have a capacity of at least two values of the associated data type. In the stream of this example, there are four queues, one for each of the four stream destinations (streaming inputs). These cues are mostly invisible to the programmer.

Once the stream C program starts executing (action), the only way the value gets into the stream is by the stream source. One of the more streams may form a directed cycle, which requires the values already contained in the stream. The simplest such cycle is
xStrm = xStrm + yStrm
Is equivalent to xStrm + = yStrm
This occurs when streams appear on both sides of the stream assignment, as in.

FIG. 9A is a first pictorial representation 400 of this assignment. Note that in this assignment, the directed cycle consists of a feedback path from the output of the + operator to one of the two inputs of the same + operator. The + operator can not consume the values from each input stream to create a value on the output stream because the values are missing on this path. Thus, as shown in the second graphical representation 402, the + operator will never fire unless the value 404 is placed on the feedback path before the start of execution.

Another problem relates to the change in offset of one single source stream to another single source stream. For example, both aStrm and bStrm are graphically represented in FIG. 9B,
aStrm + bStrm
Etc. If the input to the same module or stream expression, etc., that module or expression consumes one stream from these streams, ie one value from aStrm and one value from bStrm. When it is desired that aStrm (n) (ie, the nth reaching value on aStrm) be paired with bStrm (n + 2) (ie, the n + 2th reaching value on bStrm). Therefore, aStrm (0) is paired with bStrm (2), and aStrm (1) with bStrm (3) (the same applies hereinafter).

The solution to both problems is
<Stream identifier>. initialize (<value list>);
Provided by the stream initialization statement, which takes the form of

  When the stream C compiler / linker / loader encounters this statement, the stream C compiler / linker / loader inserts a FIFO queue into each <stream identifier> destination (if the destination is a module defined output parameter) Set the size of the queue so that it can hold at least n + 1 values of T data type (even if n is a <value list>) Where T is the data type of <stream identifier> and the values in <value list>, the first value in <value list> is the front of the queue (head Interpret this sentence as indicating that it should be queued in the order of the states to be put into).

For example, in FIG. 9A, to prevent deadlock, in graphical representation 402, the value 404 is on the feedback path and also on the equation output:
xStrm. initialize (0);
Inserted by This statement creates two FIFO queues for each destination of xStrm (the queues at the destination of the feedback path have already been inserted as described in the previous section). Assuming that xStrm is of type int, the size of each stream is at least 2 × sizeof (int), and an int value of 0 is located at the head of each queue at system initialization. This is illustrated in flow chart 402 in FIG. 9A. Thus, xStrm is initialized, and the output of substitution xStrm + = yStrm is

It becomes. AStrm to bStrm in the second graphical representation 412 in FIG. 9B
Varying the offset of is addressed in a similar manner. However, here, two values are inserted into the aStrm FIFO queue. This is because it may be desirable to offset aStrm by two values for bStrm. This means that 1 and 2 are selected as two values 414 to be inserted into the aStrm queue at system initialization, and the following stream initialization statement aStrm. initialize (1, 2);
Is achieved by using The result of this initialization is illustrated in representation 412 in FIG. 9B. Thus, xStrm is initialized and the value appearing at the output of the assignment xStrm + = yStrm is

It becomes.

As in the case of C variables, certain stream declarations are made implicit from the context, for example, by appearing as module input or output parameters, but all streams must be declared before use. The syntax of explicit stream declaration follows the syntax of C variable declaration, but the declaration in this case starts with the keyword stream.
stream <storage class identifier> _Optional <type><identifierlist>;
Here are some examples of stream declarations that do not have storage class identifiers:
stream int xStrm, yStrm;
stream char cStrm;
stream double dStrm;
Of the five C storage class identifiers: auto, register, static, extern, and typedef, in the stream declaration:
stream static int xStrm, yStrm;
Like, only static is allowed.

  Static and non-static stream declarations are determined by the context in which they appear. There are three such contexts, each with its own scoping rules. In each case, the scope rules of the stream declaration are the same as those of the counterparts of the variable declaration. For stream declarations that do not have a storage class identifier and appear inside a module, the declaration scope extends from declaration to the end of the module. For stream declarations that do not have a storage class identifier and appear outside of a module (and function), the declarative scope is global, ie visible to the whole program. For stream declarations that have static storage class identifiers and appear outside of all modules (and functions), the scope of the declaration extends from the declaration to the end of the source file where the declaration appears.

Some declarative forms relating to storage class identifiers related to variables but not to streams do not appear in this list. In C, these variables, declared with or without the auto storage class identifier, lose their value between function calls. Since streams operate only in modules, and modules are not called (modules are always in operation), autostreaming is a meaningless concept in the first place. Thus, the auto storage class identifier does not apply to stream declarations.

  A variable declaration declared using a static identifier and appearing inside a function indicates that the declared variable holds its value between function calls (function calls). However, in the case of modules, there is no notion of a call, so static identifiers are meaningless inside the module. Therefore, static identifiers are not used within module scope.

  For variable declarations, extern storage class identifiers help to distinguish between those declarations of global variables that act as declarations and definitions, and those of global variables that merely act as declarations. However, in the case of a stream, the declaration is never defined, as storage is never excluded in the stream declaration. Storage areas are allocated only at stream definition, as described in the stream FIFO section below. The storage class identifiers of register and typedef are not valid at all in streams and can not appear in stream declarations.

  A stream expression is the counterpart in the stream to a normal C expression. Apart from the fact that the input stream replaces all variables and that the output stream replaces the result, these two types of expressions are very similar. In expressions, variables and constants are combined to create new values, while in stream expressions, streams and constants are combined to create new streams. The structures of the C equation and the stream equation are almost identical. All C operators are valid operators in stream expressions. The same operator precedence applies to both C expressions and stream expressions. C function calls are also accepted in stream expressions, just as in C expressions. Instantiation of modules with a single output stream is allowed in stream expressions and is treated the same as function calls.

  The differences between equation C and the stream equation are primarily at the time and manner in which the evaluation takes place. For C expressions, evaluation occurs when the thread of control reaches a statement that contains the expression. The evaluation is done by first replacing each variable with its current value and then performing the necessary operations according to the precedence of the operator. The value returned by the last operation is then provided as the evaluation result.

  Unlike the evaluation of C expressions, the evaluation of stream expressions in the C stream programming language is not tied to the thread of control. Instead, stream expressions are evaluated opportunistically. As is conventional, the evaluation is done by performing the necessary operations according to the priority of the operators. Instead of replacing the values for the variables, the values are popped from each FIFO queue belonging to the expression input. A FIFO queue is inserted at every stream destination that is a streamed input. Evaluation is opportunistic. This is because evaluation is performed whenever there is at least one value in each input FIFO queue of the equation. As is conventional, the result produced by the evaluation is the value returned by the last operation. However, the results are dealt with differently than in the case of the C formula. For C expressions, the usage in which the result is substituted is determined by the context of the expression. For stream expressions, the result is simply assigned to the output stream of the expression (which may or may not have a name, depending on whether the expression is a substitution).

The following equation xStrm * yStrm + 5 * zStrm, where xStrm, yStrm, and zStrm are all int type streams.
Can be shown in The values reaching these three streams begin as follows:

Then the first three values assigned to the (without a name) output stream of xStrm * yStrm + 5 * zStrm are as follows:

In stream expressions, stream assignment is particularly noted. There are two types of such stream assignment, and the first type is <stream identifier> = <stream expression>
It has the form of

  As with its counterpart in C, that is, assignment to a variable, this type of stream assignment has side effects. In addition to supplying values to the output stream, stream substitution makes the output of the right-hand (RHS) expression the source of the left-hand-side (LHS), and during the process Let the output stream of RHS expression be the output stream of substitution. Stream substitution also gives a name to the output stream of the RHS expression if the output stream does not have a name. The name is not required for the output stream of the larger expression subexpression, but the name is essential if the output stream has to be addressed to a destination outside of any containing superexpression.

The formula substitution statement in the partial coat below is an example. A stream expression becomes a stream statement when a semicolon is added at the end, in both assignment and other cases.
int F (int, int);
int G (int);
stream int M (int xStrm, int yStrm)
{
.
.
.
out = F (xStrm, G (yStrm));
.
.
.
}
Formula F (xStrm, G (yStrm)) and subexpression G (yStrm) each have a stream statement as a stream expression. For G (yStrm), the output stream has no name. Because the destination of the stream is apparent from the context of the expression. That is, the destination is the second input argument of the function F in the super expression F (xStrm, G (yStrm)). However, in the case of an output stream of F (xStrm, G (yStrm)), a name is required. Because the destination is outside the expression. Its name is the assignment expression out = F (xStrm, G (yStrm))
Assigned at By this substitution, the output of F (xStrm, G (yStrm)) becomes the source of zStrm, and zStrm has a single destination, the output parameter of module M.

The second type of stream assignment is
(<List of stream identifiers separated by commas>) = <Module instantiation>
Take the form of This type occurs when it is desired to make the output of multiple output modules the source of a stream with multiple names. To illustrate, if the first output of tap is the source of int stream x and the second output of tap is the source of int stream y, the following multiple output module stream (int, int) tap (int, int, int);
It is. This is stream assignment (int x, int y) = tap (arg1, arg2, arg3);
Is achieved using By this substitution, the ith output of the module becomes the source of the ith stream, and if the output stream of the module does not have a name, the output stream is given a name.

  The statements in the module body fall into two categories: threads and streams. Stream statements deal with streams but not variables. Thread statements deal with variables, and in some cases also streams. Sentences in the thread domain are mostly C sentences, and like C sentences, are essentially imperative (procedural) and define step-by-step procedures. The sequential flow of control (often referred to as a thread) is associated with such a procedure and governs the order in which statements are executed. In contrast, stream statements are declarative. Each such statement declares a stream that appears in the statement. There is no notion of a step-by-step procedure as in the thread domain, so the order of stream statements within the module body is not important, with one exception. Just as variables need to be declared before use, streams must also be declared before use.

Due to the nature of the stream domain, there is no counterpart to those C statements that handle control flow, in particular if-else, else-if, switch, for, while, do-while, break, continue, goto, and return. In fact, the only sentence type in the stream domain is the counterpart in the stream to a C expression sentence, and as in C, the most common expression sentence is an assignment sentence. The stream expression statement has the following two forms <stream expression>;
stream <stream expression>;
Have one of the On the other hand, the stream assignment statement has the following two forms <stream identifier> = <stream expression>;
stream <stream identifier> = <stream expression>;
(<List of stream identifiers separated by commas>) = <Module instantiation>
Have one of the

Examples of applications that use modules, stream instantiations, stream declarations, stream expressions, and stream statements are finite impulse response (FIR) filters, a syntax commonly used in digital signal processing. FIR filters convert discrete time input signals into discrete time output signals. FIG. 10 is a diagram of a 5-tap FIR filter 500, where X (z) represents discrete time input 502 and Y (z) represents discrete time output 504. FIG. A series of unit delays 506, denoted z ⁻¹ , each delay the received discrete time signal by one clock cycle. A series of multipliers 508, each multiplying the received discrete time signal by a constant factor h (i). Finally, a series of adders 510, labeled Σ, each adding two received signals. The filter 500 is referred to as a 5-tap filter. This is because each of the five delayed versions of the received discrete time signal is multiplied by a separate coefficient, and as a result, the five resulting products are added.

Discrete time signals are represented as a stream of samples. Each of multiplier 508 and adder 510 is represented as a stream equation. Unit delays are represented as stream instantiations. By initializing a stream having one or more values, the values are offset (delayed) within that stream relative to the values in the second stream. This is the principle underlying the operation of the UnitDelay module.
stream int UnitDelay (int X)
{
out = X;
out. initialize (0);
}
In the body of UnitDelay, a stream assignment statement out = X;
Thus, X, which is an input stream of UnitDelay, becomes a source of out which is a default output stream of UnitDelay. On the other hand, the stream initialization statement out. initialize (0);
Inserts the value 0 into out at system initialization. This initial value in out has the effect of offsetting (delaying) all subsequent values in out by one value.

The following is a stream C implementation of a 5-tap FIR filter, such as filter 500 in FIG. 10, containing 10, 20, 30, 40, and 50 as 5 arbitrarily selected filter coefficients.
stream int UnitDelay (int X)
{
out = X;
out. initialize (0);
}

stream (int xOut, int yOut) tap (int
xIn, int yIn, int h)
{
xOut = UnitDelay (xIn);
yOut = yIn + h * xOut;
}

stream int FIR5 (int X)
{
(Int x2, int y2) = tap (X, 10 * X,
20);
(Int x3, int y3) = tap (x2, y2, 30);
(Int x4, int y4) = tap (x3, y3, 40);
(Int, out) = tap (x4, y4, 50);
}

  This implementation shows parallelism, but without using explicit parallelism syntax. This parallelism emerges from a code similar to a normal sequential code except for the output of taps with multiple names. Instead of variables, here a stream exists.

Each of the four instantiations of tap within the body of FIR 5 has the formula yIn + h * xOut
Compute its own copy in parallel with the three other tap instantiations. This is made possible by the opportunistic nature of stream expressions, and by the continuous arrival of new input values into each of the tap's instantiations. These new values are provided by the five internal streams of FIR5.
X conveys a value from the input of FIR 5 to the input of the first tap.
x2 and y2 convey values from the output of the first tap to the input of the second tap.
x3 and y3 convey values from the output of the second tap to the input of the third tap.
x4 and y4 convey values from the output of the third tap to the input of the fourth tap.
The input h of each instantiation of tap is replaced by a constant. This causes the stream C compiler to replace all instances of h in the tap instantiation with constants. All operations performed by the instantiation of tap convert the FIR5 input values to FIR5 output values.
These last output values are provided by the default output stream of FIR5.
out conveys a value from the output of the fourth tap to the output of FIR5.
This implementation is one example of how many digital signal processing functions are handled in stream C.

In the example FIR filter described above, five coefficients are known at compile time: 10, 20, 30, 40, 50. However, if the FIR5 coefficients are unknown at compile time, or if the coefficients are constant over time, but are changed from time to time, other techniques need to be used. In such a case, these pseudo constants are not true constants because they change, and they are not true streams because they are not consumed (streamed from a FIFO queue) by a stream expression or thread.

  Pseudo-constant streams are similar to regular streams in some aspects. The pseudo-constant stream has a type, one or more sources, one or more destinations, and a name. The pseudo-constant stream conveys the specified type from the specified source to the specified destination. However, in some respects, pseudo-constant streams differ from regular streams. Whereas a regular stream has a FIFO queue, a pseudo-constant stream has a storage area for one value of the specified type (very similar to the storage area associated with a variable). The values present in such storage areas continue to stay in the storage area without being popped or consumed when accessed by a streaming expression or thread. The stored values are updated as new values enter the stream from one of the stream sources. When involved, the new value simply overwrites the old value. Because this update is typically made asynchronous to system operation, the point at which the update is recognized at the stream destination is generally non-deterministic. The declaration of a pseudo-constant stream must specify an initial value to be stored in each stream location at system initialization.

The pseudo-constant stream has the following syntax, either in the singleton declaration or in the module's input or output parameter list:
const <stream type><streamidentifier> = <initial value>
Declared using. The existing C keyword const, which normally applies only to variables, indicates that the stream being declared is a pseudo-constant stream (the use of const saves the effort of introducing a new keyword).

These ideas are illustrated in the following modifications of the FIR5 module. Here, the five coefficients in the original example, namely 10, 20, 30, 40 and 50, are replaced by five pseudo constant streams h0, h1, h2, h3 and h4. Because the initial values inserted into these streams at system initialization are identical to the original coefficients, the new FIR 5 starts operating with the same coefficients as the original. However, for the new FIR5, these coefficients can be updated if the situation permits.
stream int FIR5 (int X, const int h0
= 10,
const int h1 = 20,
const int h2 = 30,
const int h3 = 40,
const int h4 = 50,
{
(Int x2, int y2) = tap (X, h0 * X, h1);
(Int x3, int y3) = tap (x2, y2, h2);
(Int x4, int y4) = tap (x3, y3, h3);
(Int, out) = tap (x4, y4, h4);
}

FIG. 11A shows module 600 with a series of FIFO buffers 602 on input stream 604 highlighted. 11B and C show two additional alternative implementations using FIFO buffer 602 and module 600. 11B shows the FIFO buffer 60.
State 2 is used only on a series of output streams 606. FIG. 11C shows the FIFO buffer 602 being used on both the input stream 604 and the output stream 606. From the programmer's point of view, the three figures shown in FIGS. 11A to C are equivalent. From a performance point of view, having buffers at the input and output as in FIG. 11C allows the module 600 to be scheduled without considering the available space on the module 600 that receives the stream. This is realized by the cost of additional memory and additional scheduling steps. FIFO buffer 602 may reside on virtual memory space, physical memory space, and registered file space, depending on the implementation.

One example of a high level scheduling algorithm for an input stream FIFO as in FIG. 11A is shown below.
a. Schedule a module to run if:
Data is present in the input FIFO (s) of the input stream (s)
and
Available space in the module's input stream FIFO connected to the current module's output stream
}

One example of a high level scheduling algorithm for an output stream FIFO as in FIG. 10B is shown below.
b. Schedule a module to run if:
There is data in the output stream FIFO of the module connected to the input stream (s) of the current module
and
Available space in FIFO of output stream (s)
}

One example of a high level scheduling algorithm for the input and output stream FIFOs as in FIG. 10C is shown below.
c. Schedule a module to run if:
Data is present in the input FIFO (s) of the input stream (s)
and
(Available space exists in the input stream FIFO of the module connected to the output stream of the current module
Or
Available space in FIFO of output stream (s)
}
thread

  Threads provide the essential capabilities needed to make stream C a complete and comprehensive language. A thread is in the body of a C function (ie a function whose input is a discrete value and whose output is a single value) or a module (ie a function whose input and output are a stream of values) It can appear in the body of the. These two types of threads are the same except that threads in the body of the module can access stream C stream (usually access stream C stream), and for that reason they do not normally terminate. . Also, the threads in the body of the C function do not access the stream C stream and terminate like all C threads (showing good behavior).

  A striking property of stream C threads is the complete departure from parallel problems. There is no parallel syntax, no direct interaction with other threads, and no new threads are created. Therefore, as for the stream C thread, it is not necessary to be aware that the stream C thread is operating in a multi-thread environment. Thus, programmers working in the thread domain may focus strictly on serial issues.

  The function declarations and function definitions in stream C have the same syntax and semantics as their counterparts in C. For function calls in stream C, the syntax and semantics depend on whether the call appears (a) in the body of the function or (b) in the stream expression. Stream C function calls in the same function (recursive function) body, or in the body of other functions, have the same syntax and semantics as normal C function calls. Stream C function calls in stream expressions have the same syntax as C function calls, except that the stream replaces variables in the function call arguments. The semantics of such calls are the same, but not the semantics of normal function calls. The differences relate to how each evaluation (call) of the function is performed. More specifically, the difference is that (1) how values are obtained for parameters (streams) that appear in function call arguments, (2) destination of function call output, and (3) control It relates to how it is handled.

  In C, all parameters appearing in arguments appearing in function calls are variables, and the value assigned to the function input variable is the current value of that variable. In stream C, all parameters appearing in the arguments of the stream expression function call are streams, and the value assigned to each of such function input streams is (a) in the case of a normal stream, from the FIFO queue in the stream destination It is either a value that is popped (consumed) or (b) in the case of a pseudo-constant stream, it is the current value at that stream destination.

  In C, the value changed by the function call is passed to the function caller. In stream C, the value returned by the stream expression function call is assigned to the function call output stream (which may or may not have a name). Because it is a stream expression itself, stream expression function calls always have an output stream. The destination of the output value is determined by the destination of the stream.

  In C, a function is called when the thread of control encounters a call for that function. In stream C, streamed function calls are evaluated regardless of the control thread (ie, the function is called). Instead, the function is opportunistically called whenever there is at least one value in each FIFO queue of the normal input stream of the function call. The pseudo-constant input stream is always ready to supply a value, and thus never prevents the evaluation of a function call or stream expression.

  Apart from these three differences, the semantics of normal C function calls and streamed function calls are the same. This means that in both cases thread-based semantics apply to function execution.

One example of a thread in a C stream with the following definition of function GDC and module GDC4 may be shown.
int GCD (int a, int b) // Recursion function {
if ((a> = b) && (a% b) == 0) // Start of thread
{
return (b);
}
if (a <b)
{
return GCD (b, a); // Function call
}
return GCD (b, (a% b)); // Function call}
stream int GCD4 (int w, int x, int y,
int z) // module {
out = GCD (GCD (w, x), GCD (y, z)); / / Stream expression with / 3 function calls}

GCD, a classic example of a recursive function, returns the greatest common divisor of two integers. GCD has two integer inputs a and b and returns one integer result. GCD 4 has 4 integer stream inputs, w, x, y and z, and has 1 integer stream output. Stream expression statement out = GCD (GCD (w, x), GCD (y, z));
Exist in the body of GCD4, and stream expression GCD (GCD (w, x), GCD (y, z))
Is present in this sentence.

  Since this equation includes the destinations of streams w, x, y and z, there is a FIFO queue at each of these four destinations. These queues allow the function calls GCD (w, x) and GCD (y, z) to be evaluated (implemented) opportunistically and in parallel as described above. Like these two calls, the third call to the GCD is opportunistically performed using the input values obtained from the FIFO queues of the two input streams. These input streams were created as output streams of two other calls to GCD, so that the FIFO queues on these two streams are such that the third call to GCD is the first two calls. Allows to be performed in parallel. The output stream of this third function call is directed to the output stream of GCD 4 by stream assignment to out. This configuration of function calls to GCD, represented in the data flow diagram in FIG. 12, is such that data from four input streams, w, x, y and z, are streamed through three parallel operation function calls , And as a result, the maximum of w (i), x (i), y (i), and z (i) for several integers i, each output value being i> = 0 A stream of output values is created, which is a common divisor.

  From the stream point of view, it is not important how the module converts input stream values to output stream values. What is important is only the transformation (s) from input to output (and any side effects). In the examples given so far, these transformations may be streamed, ie application specific hardware, reconfigurable hardware (such as in FIGS. 1 and 2), a processor that executes serial code or some other It has been expressed in terms of expressions that can be implemented using the mechanism of.

These transformations can be explicitly represented as sequential code present in the body of the module. Such code is stored program
It can be run on a sequential processor) and can be in what can be referred to as a thread domain. The body of the module will typically exclusively contain statements in the stream domain or thread domain, but this does not exclude both types of statements within the same module body. In that case, the two domains operate side by side (i.e. in parallel).

  The syntax and semantics of the thread domain are: Kernighan and Dennis M. It is a superset of the C language, informally defined by Ritchie, co-authored "C Programming Language" (1978), and officially defined by the ISO C standard ISO / IEC 9899. Additions to the standard C language allow threads to access module input streams, module output streams, streams internal to the module body, or global streams that are visible to threads Relates to the action to be taken. These stream access operations fall into two categories: block and non-block. To understand these operations, the mechanism used to regulate the flow of values in the stream, and the mechanism for managing tasks (tasks are equivalent to module instances) refer to the node wrapper in Figure 4 It is important as I explained.

  Flow control and task management are important services provided by the Stream C runtime support system. Flow control prevents FIFO queue overflow (i.e. writing data to a queue that is already full) and FIFO queue underflowing (i.e. reading data from a free queue). Task management controls when the task is put into execution state, and in some cases when the task execution is ended. In the stream C flow control system and the task management system, there are three key elements: consumer count, producer count, and task manager.

  An integer consumer count is associated with each FIFO queue of a normal (not pseudo-constant) stream. All reads by a particular thread in a particular stream access the same FIFO queue, and thus access the same consumer count. The consumption count sign bit indicates whether the FIFO queue is empty. A sign bit of 1 (consumer count is negative) indicates that the queue is empty. A sign bit of 0 (consumer count is non-negative) indicates that the queue is non-empty.

  An integer producer count is associated with each source of each normal (not pseudo-constant) stream. The sign bit of the producer count indicates whether there is space available in the downstream FIFO queue to receive the value inserted into this stream source. A sign bit of 0 (creator count is non-negative) indicates that not all downstream queues have space for receiving values in this output stream. A sign bit of 1 (creator count is negative) indicates that all downstream queues have space to receive values in this output stream.

Each processing core, such as node 180 in FIG. 2, has a task first-in-first-out ready-to-execute key with all resources including the input data needed to begin execution. Each processing core has a task manager that manages the execution of tasks and provides the necessary adjustment signals between tasks. The task manager increments the consumer count when data is pushed (written) to the FIFO queue and decrements the consumer count when data is popped (consumed) from the FIFO queue And send a backward acknowledgment to the stream source to indicate that space is available in the destination FIFO queue (default is to send backward acknowledgment after each value has been consumed from each FIFO queue) Send automatically). The task manager increments the creator count of the stream when data is written to the module's output stream, and the creator count of the output stream when a backward acknowledgment is received for the module's output stream. Decrementing and placing the task in the processing core's ready-to-execute task queue if the task has input data and any other required resources that the task requires to proceed , Also run. The task manager puts the task into execution if the task is at the top of the ready-to-execute task queue and the execution unit is available, or if the task does not have the input data required to proceed Stop execution of the task if it times out.

  A block type stream access operation is such that a thread appearing in a module body accesses a stream that is visible to threads, such as a module input stream, a module output stream, a stream internal to the module body, and a global stream. Make it possible. These are the preferred methods to access the stream. This is because, unlike the non-block type stream access operation, the block type stream access operation does not cause nondeterminism. Such blocks of operations and non-blocks are handled automatically by the task manager of the processing core.

There are three such operations, each of which was created after a similar operation in C ++. The operator >> is used to pop (consume) a single value from the stream FIFO queue and assign that value to a variable. The operator >> is <stream identifier>>><variableidentifier>;
Used in sentences of the form This statement pops a single value from the left stream and assigns it to the right variable. However, if the FIFO queue for the stream is free as indicated by the stream's consumer count's sign bit, then the statement is blocked (stalled) and the queue is indicated by the stream's consumer count's sign bit. It is held in a blocked state until it becomes non-empty again.

The operator << is used to assign the current value of a variable to a stream. The operator << is
<Stream identifier><<<variableidentifier>;
Used in sentences of the form This statement assigns the value of the right variable to the left stream. However, if one or more downstream queues do not have space to receive such data, as indicated by the creator count's sign bit in the stream source, the statement is blocked (stalled) and all downstream It is held blocked until the side queue has space again to receive the value as indicated by the sign bit of the stream's creator count.

The peek operator is used to obtain the value at the beginning of the stream FIFO queue without popping (consumption). The peek operator is
<Stream identifier>. peek ()
Used in the formula of the form This expression returns the current value at the beginning of the <stream identifier>'s FIFO queue but does not pop (consume) values from the queue. However, if the FIFO queue for the stream is free as indicated by the stream's consumer count's sign bit, then the statement is blocked (stalled) and the queue is indicated by the stream's consumer count's sign bit It is held in the blocked state until it becomes non-empty again.

  Similar to block type stream access operators, non-block type stream access operations are such that threads appearing in a module body are module input streams, module output streams, streams internal to the module body, global streams, etc. Allows access to streams that are visible to threads. However, unlike block-type operations, non-block-type operations are typically involved in race conditions that affect the result of the operation, thus introducing non-determinism. There are two such operations.

<Stream identifier>. consumerCount ()
An expression of the form returns a consumer count of <stream identifier>. Note that <stream identifier> is a stream read by a thread via >> operation or peek operation. This expression is mainly used to test the consumer count sign bit of <stream identifier> to avoid >> operation or peek operation when FIFO queue of <stream identifier> is empty .

<Stream identifier>. producerCout ()
An expression of the form returns the creator count of <stream identifier>. Note that <stream identifier> is a stream written by a thread via << operation. This expression is to test the creator count sign bit of <stream identifier> to avoid the << operation, if one or more downstream queues do not have space to receive such a new value. , Mainly used.

The threads in the module body may take many different forms, but many variations would be the following typical form.
stream int moduleA (int strm1, ..., int strmN)
{
int var1,. . . , VarN, result; // Declare variable
while true // loop forever
{
strm1 >>var1;
// Read value from input stream
・
・
strmN >>varN;
・ / / Calculate the result
・
・
out <<result; // Assign result to output stream
}
}
Here, moduleA is a module having one or more input streams and a single output stream. The data types of the input and output streams are optionally chosen to be integer types. The first thing the threads in the body of module A execute is to declare the values for each input stream and the single output stream.
The thread is then put into an infinite loop, including (a) reading (consuming) values from each input stream, (b) calculating the result, and (c) assigning the result to the output stream. enter.
Array

  As in other languages, sequences play an important role in stream C, as well as sequences of data elements, as well as stream and module sequences. An array of actual data values (as opposed to a pointer to an array of data values) is conveyed in parallel over multiple streams. Stream arrays are particularly useful when used with an array of modules.

Stream C inherits from C syntax and semantics for data arrays. This means that when the name of the array is used as a (function) argument, the value passed to the function is the position or address of the beginning of the array, and the array element is not copied. The same is true for stream inputs (arguments) and module outputs. For illustration purposes, the GDC4 module described above may be used.
stream int GCD4 (int w, int x, int y,
int z) / / with two integer arguments {// module
out = GCD (GCD (w, x), GCD (y, z));
}
Instead of supplying GCD 4 with 4 separate integer stream arguments, a single stream argument is supplied, each value being an array of 4 integers. GCD4 will be transformed as follows.
stream int GCD4 (int * wxyz) // module with one array argument {
out = GCD (GCD (wxyz [0], wxyz [1]),
GCD (wxyz [2], wxyz [3]));
}

  According to the rules of the C language, the single argument of GCD4 is an int * type, ie a pointer to an integer, in this case the first integer in an array of 4 integers. These four integers in the body of GCD4 are accessed using the standard C language operator []. Providing a C language type data array to a module is one way to handle the array in the context of a stream.

  For some applications, supplying a stream of array pointers to the module is not sufficient to take full advantage of the application-specific parallelism. Thus, rather than a stream of arrays, an array of streams is not a pointer to an array of data values, allowing an array of actual data values to be conveyed in parallel over multiple streams. The declaration of a stream array is the same as a normal C-language array declaration, except that there are two differences: the keyword stream precedes the declaration, and that the size of the array must be known at compile time. This limitation is necessary because all streams in the application as well as modules are instantiated at compile time.

An example of a stream array declaration is given below.
stream int array1D [4];
stream int array2D [4] [16];
stream int array3D [4] [16] [9];
The first declaration declares that array1D is a one-dimensional array of four integer streams. Similarly, it is declared that array2D is a two dimensional array of 64 integer streams, and array3D is a three dimensional array of 576 integer streams. The individual streams of the stream array are accessed in the same way as the individual elements of the data array. For example,
array3D [3] [15] [7]
Indicates one of 576 streams of array3D.

Once a stream array is declared, the entire array, subarrays within the array, or individual streams within the array may be referenced. These three cases are illustrated in the partial code below.
stream int moduleA (int); // module declaration stream int moduleB (int [4]); // module declaration stream int moduleC (int [3] [4]); // module declaration

stream int moduleD (int W [3] [4]) // module definition {
・
・
・
stream int X = moduleA (W [2] [0]);
// Stream type
stream int Y = moduleB (W [2] [0]);
// Stream type
stream int Z = moduleC (W); // stream expression
・
・
・
}
Here, declarations for moduleA, moduleB, and moduleC and partial definitions of moduleD are shown. The input types of these four modules are shown below.

  The input arguments supplied to the instantiation of moduleA, moduleB, and moduleC in the body of moduleD are shown below.

In each case, the module instantiation argument type matches the module input type, so each module instantiation satisfies the strong requirement of stream C typing.

Accessing individual streams of stream arrays within a stream expression is also straightforward, as shown in this example complex multiplication module.
stream int [2] complexMult (int X [2],
int Y [2])
{
out [0] = X [0] * Y [0]-X [1] * Y [1];
out [1] = X [0] * Y [1] + X [1] * Y [0];
}
Because the operators in the stream expression are active in parallel, the stream expressions X [0] * Y [0] -X [1] * Y [1] and X [0] * Y [1] + X [1] The four multiplications, one addition, and one subtraction at Y [0] are evaluated in parallel.

  Data parallelism, one of the most prevalent approaches to parallel processing, is the same task performed in parallel (in parallel) on different parts of the same data structure (typically an array) , Is a form of parallelism. In stream C, data parallelism is supported by the module arrangement.

A module array is, as the name implies, an array of modules. A module array is declared by inserting an array dimension enclosed in square brackets between the module name and the list of input parameters. The following are two examples of module array declarations.
stream int moduleA [3] [4] (int, int);
stream (int, int) modu1eB [3] [4] (int, int);
In both cases, the array dimension is 3 × 4.

Similar to the normal (stand-alone) module definition, the module arrangement definition has a body enclosed in curly brackets ({and}). The following are two examples of module sequence definitions. The first example has a single (default) output stream, whereas the second example has two output streams with names.
stream int moduleA [3] [4] (int a, int b)
{
// Module body}

stream (int x, int y) moduleB [3] [4] (int a, int b)
{
// Module body}

  Once a module array is declared (declared or defined), the entire array, subarrays within the array, or individual modules within the array can be instantiated within the stream expression in the same manner as data arrays and stream arrays . These three cases are shown for module A [3] [4].

  An important attribute of the module array becomes noticeable when the module array is instantiated at system initialization. Each element of the module array is instantiated as a separate module instantiation. As a result, all array elements can operate in parallel. moduleA [3] [4] is an example of this concept. When a module is instantiated, 12 (3 × 4) separate instantiations of module A are created, each instantiation operating in parallel with the other 11 instantiations. Furthermore, this instantiation multiplication applies to each instantiation of moduleA [3] [4]. Thus, if there are three instances of moduleA [3] [4], 36 (3 × 12) separate instantiations of moduleA are created.

  The personalization of the module array instantiation determines which data the instantiation is to operate on. The instantiation can be personalized by supplying each module instantiation with its own unique data through the input stream of the instantiation. By allowing each module instantiation to specify its array index using the index operator, this allows the instantiation to access its own unique part of the global array , Instantiation can be personalized.

The first type of personalization that can be used to provide unique data for stream arrays to each element of a module array is shown below. The second type of personalization takes advantage of the fact that the instantiation of the array index of each array module is known at compile time. To access these indices, the programmer uses the following syntax: int index (int i)
Use operators in. In the equation, i is an integer expression that is evaluated to a constant at compile time. At compile time, index (i) is replaced with the first index of the instantiation. If i is out of array bounds, compile-time or runtime errors occur.

Stream and module arrangements provide maximum utility when stream and module arrangements are combined using the special arrangement combining function of stream C. For combining, three requirements, a) the stream array and the module array must have the same dimensions, b) the stream array must be connected (coupled) with the input or output of the module array And c) the stream array type must match the input / output type of the module.

When such a combination occurs, each individual stream in the stream array is connected (coupled) to the input / output stream of an individual module of the module array having the same index. Therefore, 0 <= i ₁ <D ₁ , 0 <= i ₂ <D ₂ . . . For 0 <= i _n <D _n , the stream array S [D ₁ ] [D ₂ ]. . . [D _n ] is a module array M [D ₁ ] [D ₂ ]. . . When coupled to the input / output of [D _n ], each individual stream S [i ₁ ] [i ₂ ]. . . [I _n ] are individual modules M [i ₁ ] [i ₂ ]. . . Is connected to the input / output _{[i n].}

The following is an example of a stream array coupled to the output of one module array and the input of another module array.
stream int moduleA [3] [2] (); // first combined module stream void moduleB [3] [2] (int); // second combined module stream void parentModule ()
{
stream int cStrm [3] [2]; // Combined stream
cStrm [] [] = moduleA [] [] (); // output of moduleA coupled to cStrm
moduleB [] [] (cStrm [] []); // cStrm coupled to the input of moduleB
}
Here, the output stream of moduleA [3] [2] is coupled to cStrm [3] [2], and cStrm [3] [2] is coupled to the input stream of moduleB [3] [2]. These are regular combinations. Because
CStrm [3] [2], moduleA [3] [2], and moduleB [3] [2] all have the same dimensions,
• cStrm [3] [2] is connected to the output of moduleA [3] [2] and the input of moduleB [3] [2],
The type of cStrm [3] [2], the output type of moduleA [3] [2], and the input type of moduleB [3] [2] are all int,
It is for.

  The following table shows each individual stream of cStrm [3] [2]: (a) a module whose output is a stream source, (b) an individual stream in cStrm [3] [2], and (c) an input stream List the modules that are the destination.

   PING

  There are situations where a module needs to notify other modules that a particular operation that the module is performing, that a side effect has been completed. For example, when a module performs an operation on a data structure in global memory, that module will typically complete the operation, perhaps as one of many modules that perform the operation on the same data structure. It is necessary to notify the downstream module that the downstream operation or task can be started. In these situations, it is not necessary to return a value, only a signal that a particular task has been completed. For those situations where a signal rather than a value is required, stream C provides the ping data type. Ping (ping type values) has no property and is completely indistinguishable from one another.

  Ping is used with three operators: (1) join operator to provide task synchronization, (2) >> stream access operator, and (3) << stream access operator. The first usage relates only to streams, while the second and third usages relate to streams and threads.

The ping keyword is used when declaring one or more ping type streams. For example, the following equation stream ping pStrm0, pStrm1, pStrm2;
Declares that pStrm0, pStrm1, and pStrm2 are ping type streams. The ping keyword is
stream ping moduleName (int, ping);
It is also used for module prototypes / definitions that declare that module inputs or outputs are of ping type.

The first usage of ping relates to the join operator, which has the ability to connect the ping stream with one or more other streams to create a single output stream. This operator is similar to the rendezvous operation found in some other arithmetic models. Expressions that include the join operator have two forms: <ping stream array>. join ()
<Ping stream>. join (<stream expression>)
Take one of the. As with all stream expressions, each evaluation of the expression in one of these forms consumes a single value / ping from each input stream, and on the output stream (without a name) of the expression Make a single value / ping. If the input stream is idle (no value present), evaluation is stalled (blocked) until all input streams have at least one value / ping. No explicit join operation is required for non-ping expressions. Because the effect of the join operation is already covered by the semantics of expression evaluation.

  When the first type of expression is evaluated, a single ping is consumed from each stream in the array of ping streams, and a single ping is issued on the output stream of the expression.

  Once the second form of expression is evaluated, a single ping from <ping stream> and an evaluation of <stream expression> are consumed. This stream expression <stream expression> may be of any type including ping. The values obtained from the evaluation of <stream expression> are issued on the output stream of the join operation. If the expression is of ping type, the expression is evaluated to a single ping. Thus, the ping stream functions as a guard that allows the progress of evaluation only when there is a ping in <ping stream>, as in the case of the above-mentioned >> operator.

  Two forms of the join operation are illustrated in FIGS. 13A and 13B. In FIG. 13A, individual streams of a one-dimensional ping stream array of size n are concatenated to create a single (nameless) output ping stream. In FIG. 13B, a single ping stream, pingStrm, is concatenated with the expression expr to create a single (no name) output stream having the same type as expr.

  One example of a join operation may include data structure X. However, for the data structure X, two operations, ie, operations A and B, are performed. These operations have the following requirements: a) neither operation A nor operation B is performed except in response to the go signal; b) operation A and operation B when the go signal is received Are performed in parallel, and c) both operations performed in response to the immediately preceding go signal must be completed before either operation A or operation B is started, Satisfy.

A simple solution to this problem is to use two instances of the join operation.
stream ping moduleA (ping pStrm)
{
while (true)
{
pStrm >>ping;
// execute operation A on data structure X
out <<ping;
}
}

stream ping module B (ping pStrm)
{
while (true)
{
pStrm >>ping;
// perform operation B on data structure X
out <<ping;
}
}

stream ping moduleC (ping goStrm)
{
stream ping startStrm = goStrm. joi
n (doneStrm);
stream ping StrmA = moduleA (startStrm);
stream ping StrmB = module B (startStrm);
stream ping doneStrm = StrmA. join (StrmB);
doneStrm. initialize (ping);
out = doneStrm;
}
moduleA and moduleB encapsulate operation A and operation B, respectively. Each has an input ping stream that starts one operation per ping and an output ping stream that confirms the completion of one operation per ping. moduleC contains one instance of both moduleA and moduleB and receives the go signal via the goStrm input ping stream.

The six sentences in module C play the following roles.
stream ping startStrm = goStrm. join (doneStrm);
Connects goStrm and doneStrm to make startStrm. Thus, if there is a ping on the goStrm (i.e. the go signal) and a ping on the doneStrm (which indicates that operations A and B have been completed in response to the previous go signal): ping is assigned to startStrm.
stream ping StrmA = moduleA (startStrm);
Connects startStrm to the input ping stream of moduleA and connects the output ping stream of moduleA to StrmA. This means that operation A is performed in response to the go signal only after both operations associated with the previous go signal have been completed.
stream ping StrmB = module B (startStrm);
Is similar to the previous sentence, and this sentence ensures that the operation B is performed in response to the go signal only after both operations associated with the previous go signal have been completed. . However, the order in which the operation A and the operation B are performed is not limited. In other words, the operation A and the operation B are performed in parallel.
stream ping doneStrm = StrmA. join (StrmB);
Connects StrmA, which is the output ping stream of moduleA, to StrmB, which is the output ping stream of moduleB. Thus, if both operations performed in response to the previous go signal are complete, ping is substituted for doneStrm.
doneStrm. initialize (ping);
Assigns a single ping to doneStrm at system initialization. This indicates that all previous operations have been completely absent. Without this statement, moduleC will deadlock and no operation will be performed at all.
out = doneStrm;
Connects doneStrm to out which is the default output stream of moduleC. Each ping on this stream confirms that operations A and B performed in response to the go signal are complete. The behavior of module C is summarized as a go signal (ping) on the input port of module C so that operations A and B can be performed in parallel with respect to data structure X only after the previous operations have been completed. When both operation A and operation B are complete, module C sends ping as a confirmation on its output port.

pingStrm >>ping;
The statement in the form (where pingStrm is a ping-type stream) has the ability to synchronize the execution of a thread with the ping in pingStrm. When this statement is encountered in a thread, a single ping is read (spent) from pingStrm. If pingStrm is free (ie, there is no ping in pingStrm), this statement is blocked (stall) until a ping is available. Thus, this statement acts as a guard that only allows the thread to progress when the ping is in pingStrm. In this operation, no variable is involved, and >> Only the keyword ping exists to the right of the operator that is normally expected to exist.

pingStrm <<ping;
The statement in the form (where pingStrm is a ping-type stream) allows the thread to inform interested parties that a particular operation or operations have been completed. When this statement is encountered in a thread, a single ping is written to (assigned to) pingStrm. Unlike the first sentence above, this sentence is never blocked.

These two forms of stream / thread interaction involving ping are illustrated in the partial code below.
stream ping moduleA (ping pStrm)
{
// Initialize before entering loop
while (true)
{
pStrm >>ping;
// Perform operations with side effects
out <<ping;
}
}
moduleA has a single input port and a single output port, both of which are pinged. In module A, there is a thread including an infinite loop. Note that each iteration of this infinite loop has the following statement: pStrm >>ping;
It is started by This statement has the function of synchronizing the iterations of the loop with the pings in the module input stream pStrm. When pStrm is idle, this sentence is blocked, and when pStrm is non-empty, this sentence consumes a single ping from pStrm. That sentence is followed by a sentence that is always related to activities with side effects. If there are no side effects, modleA will be equivalent to inoperable. At the end of each iteration, the following statement out <<ping;
Exists. Note that this statement informs other loop iterations through the standard output port of moduleA.

The join operator is useful when working entirely in the stream domain. However, there may be situations where it is more convenient to perform coupling within a thread. For example, thread stream ping pingStrm [32];
Consider combining individual streams within. It can be achieved by embedding a for loop in the thread.
for (int i = 0; i <32; ++ i)
{
pingStrm [i] >>ping;
}
This loop is blocked until one ping is consumed from each of the 32 streams in pingStrm. pingStrm []. The output stream corresponding to the output stream of join () is the statement joinStrm <<ping;
It is made by following a for loop with.

pingStrm []. These two partial codes are embedded in a while (true) loop to create a module that mimics the behavior of join (), which is the module stream ping joinArray (ping pingStrm [32])
{
while (true)
{
for (int i = 0; i <32; ++ i)
{
pingStrm [i] >>ping;
}
out <<ping;
}
}
Assigned to

The module with the embedded thread is pingStrm. It can be used to mimic the behavior of join (expr), where expr is an expression. However, in this case, the module needs not only the input stream for pingStrm but also the input stream for each input stream of expr. Thus, for example, if expr is the expression X * Y + Z, where X, Y and Z are integers, then pingStrm. The module that implements join (expr) is
stream ping joinExpr (ping pingStrm, int X, int Y, int Z)
{
while (true)
{
pingStrm >>ping;
out << X * Y + Z;
}
}
It will be like.

The pixel processing example is a form of parallelism, a ping in the implementation of data parallelism, a stream in which the same task is performed in parallel (parallel) on different parts of the same data structure such as an array, etc. The use of sequences and module sequences is shown. This example consists of a module arrangement and modules.
extern int xScaleFactor, yScaleFactor;
stream ping doPixel [64] [256] (int * baStrm) // The body is {// the thread domain
const int x = xScaleFactor * index (0);
const int y = yScaleFactor * index (1);
int * baseAddress;
while true
{
baStrm >>baseAddress;
・ / / Operation baStrm [x] [y] and
. // // Do it in the vicinity
・
out <<ping;
}
}

stream void parentModule (int * baStrm) // The body is {// the stream domain
stream ping xStrm [64] [256];
stream ping jStrm;
jStrm. initialize (ping);
xStrm [] [] = doPixel [] [] (jStrm.join (baStrm));
jStrm = xStrm [] []. join ();
}

  The two-dimensional module array doPixel [64] [256] is made to match the size of the two-dimensional array of pixels. The base address of the pixel array on which doPixel [64] [256] operates is supplied by the input stream baStrm. The x-coordinates of the pixels on the individual doPixel module are obtained by multiplying the global constant xScaleFactor with index (0) (see section 5.3), which is the x index of the individual doPixel module. The y-coordinate of the pixel on the individual doPixel module is obtained by multiplying the global constant yScaleFactor with index (1), which is the y index of the individual doPixel module. The processing of each pixel begins by setting the variable baStrm to the current value of baStrm. Next, operations are performed on baStrm [x] [y] and its neighborhood. Once processed, the individual doPixel module signals completion by issuing a ping.

The parentModule is responsible for broadcasting the base address of the pixel array to the individual modules in doPixel [64] [256]. The following statement xStrm [] [] = doPixel [] [] (jStrm.join (baStrm));
It is done by Here, the expression jStrm. In the input argument list of doPixel. join (baStrm) acts as a guard, allowing values in baStrm to pass only if there is a ping on jStrm. The following statement jStrm. initialize (ping);
The initial ping, which is inserted into jStrm by, allows just the first base address to pass undisturbed. Then ping is as follows: jStrm = xStrm [] []. join ();
(Here, xStrm [64] [256] is an array of ping streams created by the individual modules in doPixel [64] [256]) and is inserted into jStrm. Thus, a new ping is inserted in jStrm only if all modules in doPixel [64] [256] signal the completion of the previous operation by issuing a ping. This ensures that all operations on the pixel array are completed before operations on the next array begin.

  There are significant advantages to using ping rather than the standard C data type. With the C data type, first in, first out (FIFO) is required for data values at all destinations of the C data type stream, ie, at every position where the stream is an input to the expression. However, because pings are indistinguishable from one another, all that is required at each destination of the ping stream is a counter that tells the number of pings queued. This results in a significant cost reduction compared to a first-in-first-out queue for data values.

The pragma command is an instruction to the stream C compiler / linker / loader. The instruction #pragma InitializeCount (m, p, n) initializes the consumption / creation side count of the input / output port p of the modules m to n. The pragma command must immediately follow the module definition #pragma FwrdsAckValue (m, s, n). This definition specifies n as the forward acknowledgment value for point-to-point connections starting from output stream s of module m. The pragma command specifies n as the backward acknowledgment value for point-to-point connections starting from output stream s of module m. #pragma BwrdsAckValue (m, s, n)
It must follow right after. The pragma command must immediately follow the module definition.

  Some example benefits of the above concept are the support of threads and multithreading, i.e. parallel execution of multiple threads. In addition, all forms of parallelism such as SIMD, MIDM, instruction level, task level, data parallelism, data flow, and Systolic can be represented. Deterministic behavior is the default. Nondeterminism is added explicitly only when needed for the program. The reason is that what makes software test easiness and reliability more effective is in sequential programming. The concepts described above do not have explicit parallel syntax. Parallelism falls out of code in similar stream domains, at least in terms of syntax, to regular sequential code. Thus, programmers working in the thread domain may focus strictly on sequential issues. The programming model is useful for model-based design and model-based testing, scaling with any number of processing cores. The programming model is equally applicable when the distance separating the processing cores is in nanometers or thousands of kilometers. There are no foreground or background tasks, only tasks, no interrupts or message passing, only streams.

Although the invention has been described with reference to particular embodiments according to the invention, these embodiments are merely exemplary and do not limit the invention. For example, a node may include any type of processing unit, functional circuit or collection of one or more units, and / or resources such as memory, I / O elements, and the like. The nodes may be simple registers, or more complex, such as digital signal processing systems. Other types of networks or interconnection schemes may also be used, not described herein. The features or aspects of the invention may also be achieved in a system other than the adaptation system described herein with respect to the preferred embodiments.
The embodiments of the present invention include the following inventions (corresponding to claims 1 + 6 at the time of application), but are not limited thereto:
<Invention 1>
A system that performs stream-based computer source code conversion so that execution of runtime operation of a multi-core computer system is efficiently operated,
A memory device for storing stream based computer source code, comprising:
The source code includes one or more module definitions, and each module definition includes a list of input streams, a list of output streams, and a body.
With multiple processing cores,
A conversion system that includes at least one of the plurality of cores, for the conversion system to execute on the one or more processing cores from the stream-based computer source code. Create a collection of tasks, and each task is either a module definition with a thread domain body in the source code or a module definition with a stream expression in the source code An executable version of the task, the task further comprising an input stream and an output stream corresponding to the source code module definition or the streamed input stream and output stream,
things and,
System with
<Invention 6>
A system according to Invention 1;
The transformation system assigns zero or more tasks to be performed to each processing core,
Each processing core includes a task manager that manages the execution of each of the tasks assigned to the respective processing core,
system.

Claims (20)

A system that translates stream-based computer source code to efficiently execute the execution of runtime operations of a multi-core computer system, comprising:
A memory device for storing stream based computer source code, comprising:
The source code includes one or more module definitions, and each module definition includes a list of input streams, a list of output streams, and a body.
With multiple processing cores,
A conversion system that includes at least one of the plurality of cores, for the conversion system to execute on the one or more processing cores from the stream-based computer source code. Either zero or more tasks , each task being a module definition with a thread domain body in the source code or a module definition with a stream expression in the source code The executable version, the task further comprises an input stream and an output stream, and the input stream and the output stream respectively are module-defined input stream and output stream, or stream- type input For streams and output streams,
things and,
System with   The system according to claim 1, wherein the source code includes function definitions having variables as inputs and outputs, wherein the function definitions and the module definitions are distinguishable from one another. The system according to claim 1, wherein each task is
When the data value is available, the task when it encounters the instruction for obtaining a data value from the input stream of the task, to consume the data values from the first-in first-out queue in the input stream of the task,
Task, a data value, when encountering the instructions for placement in the output stream, the data value, Ru is arranged on the output stream of the task,
system. The system according to claim 1, wherein each task corresponding to a stream expression is
When the data value is available from the first-in first-out queue in the input stream of the task, to consume the data value,
Every time the stream formula Ru is evaluated, the data values, Ru is arranged on the output stream of the task,
system. The system according to claim 1, wherein the stream based computer source code specifies module definition and stream type interconnection, and the module definition is defined in the computer source code or the included library. The stream expression is identical to the C expression computer program expression containing the variables , except that it is an instance of, and the variables are replaced by the stream in the stream expression , and the interconnection is
Input stream module definition in the input stream module instance or stream type,
To the input stream module instance or stream type, module instance or stream type of the output stream, or,
To the module definition of the output stream, the module instance or stream type of the output stream,
Consisting of streams connecting one or more of
system. The system according to claim 1, wherein
Each processing core includes a task manager that manages the execution of each of the tasks assigned to the respective processing core,
system.   The system of claim 6, wherein the task manager manages task execution on a plurality of processing cores. The system according to claim 6, wherein
The task manager
Consumer against the input stream of the task (consumer) count,
Production side count of the output stream of the task,
Ready-to-run queue, ready-to-run queue,
An input count for each task that determines the number of input streams for that task that are required to be enabled to prepare the task for execution;
An output count for each task, which determines the number of output streams of that task that are required to be enabled to prepare the task for execution.
Maintain the system. The system according to claim 1, wherein the stream based computer source code comprises a stream enhanced to a first-class status.
The position of the first class, stream identifier, the input parameters of the function, the output of the function, and allow it to be constrained such that parameters or outside expressions in a system.   The system of claim 1, wherein the stream-based computer source code comprises a ping stream that conveys pings that do not have associated data values from the ping stream source to the ping stream destination. system. The system of claim 1, wherein stream-based computer source code includes an assignment statement that causes the output stream of the stream expression to be the source of a second, previously declared stream. system.   The system of claim 1, further comprising an interconnection network carrying data values between the memory device and a plurality of processing cores, wherein the interconnection network and the plurality of processing cores are a runtime system. Configure the system. A method performed by the multi-core computer system for converting stream-based computer source code to efficiently operate the execution of runtime operations of a multi-core computer system including multiple processing cores, comprising:
Storing stream-based computer source code in a memory device, the source code comprising one or more module definitions, each module definition comprising a list of input streams, a list of output streams, and With one having the body,
Generating zero or more tasks for execution on one or more processing cores from stream-based computer source code, each task comprising a thread domain body within the source code; An executable version of either an accompanying module definition or a module definition with a stream expression in source code, the task further comprising an input stream and an output stream, each of the input stream and the output stream but the input and output streams of the module definition, or, corresponding to the input and output streams of a stream type,
Performing the generation of zero or more tasks on a plurality of processing cores to perform runtime operations;
Method including.   14. The method of claim 13, further comprising: conveying data values between the plurality of processing cores and the memory device via an interconnection network.   The method according to claim 13, wherein the stream-based computer source code comprises function definitions having variables as input and output, wherein the function definitions and module definitions can be distinguished from one another. The method of claim 13, wherein each task is
When the data value is available, the task when it encounters the instruction for obtaining a data value from the input stream of the task, to consume the data values from the first-in first-out queue in the input stream of the task,
Task, a data value, when encountering the instructions for placement in the output stream, the data value, Ru is arranged on the output stream of the task,
Method. The method according to claim 13, wherein each task corresponding to a stream expression is
When the data value is available from the first-in first-out queue in the input stream of the task, to consume the data value,
Every time the stream formula Ru is evaluated, the data values, Ru is arranged on the output stream of the task,
Method. The method according to claim 13, wherein the stream based computer source code specifies module definition and stream type interconnection, and the module definition is a computer source code or a module defined in an included library. The stream expression is identical to the C expression computer program expression containing the variables, except that it is an instance of, and the variables are replaced by the stream in the stream expression , and the interconnection is
Input stream module definition in the input stream module instance or stream type,
To the input stream module instance or stream type, module instance or stream type of the output stream, or,
To the module definition of the output stream, the module instance or stream type of the output stream,
Consisting of streams connecting one or more of
Method. The method according to claim 13, wherein the stream based computer source code comprises a stream enhanced to a first-class status.
The position of the first class, stream identifier, the input parameters of the function, the output of the function, and allow it to be constrained such that parameters or outside expressions in, and a method. A programmable computing device,
With multiple processing cores,
A memory device for storing stream-based computer source code, wherein the source code comprises one or more module definitions, each module definition comprising a list of input streams, a list of output streams, and a body (body With)),
A converter coupled to the memory device, wherein the converter performs zero or more tasks from stream-based computer source code for execution on one or more processing cores And each task is an executable version of either a module definition with a thread domain body in the source code or a module definition with a stream expression in the source code, and further comprising an input and output streams, each of the input and output streams are input and output streams of the module definition, or correspond to the input and output streams of a stream type,
The converter selects one of the plurality of processing cores for each of the zero or more tasks , wherein the plurality of cores are for zero or more tasks in parallel with execution of the run-time operation. A computing device that performs generation.

Images