Patent Publication Number: US-9430427-B2

Title: Structured block transfer module, system architecture, and method for transferring

Description:
RELATED APPLICATIONS 
     This application is a continuation of U.S. application Ser. No. 11/607,474 filed on Dec. 1, 2006 (now issued as U.S. Pat. No. 8,706,987), entitled “Structured Block Transfer Module, System Architecture and Method for Transferring,” which are incorporated by reference herein in its entirety. 
     This application is related to U.S. application Ser. No. 11/607,481, filed on Dec. 1, 2006 (now abandoned); U.S. application Ser. No. 11/607,429 filed on Dec. 1, 2006 (issued as U.S. Pat. No. 8,289,966 on Oct. 16, 2012); U.S. application Ser. No. 11/607,452 filed on Dec. 1, 2006 (issued as U.S. Pat. No. 8,127,113 on Feb. 28, 2012); and U.S. application Ser. No. 13/358,407 filed on Jan. 25, 2012; and U.S. application Ser. No. 14/193,932 filed on Feb. 28, 2014; which are incorporated by reference herein in their entirety. 
    
    
     FIELD OF THE INVENTION 
     This invention pertains generally to systems, devices, and methods for processing data or other information in a multiple processor or multiple processor core environment using shared memory resources, and more particularly to systems, devices, and methods for processing data in such environments using a structured block transfer module, system architecture, and methodology. 
     BACKGROUND OF THE INVENTION 
     Increasingly, multiple-processor-based systems as well as processors having multiple cores are being deployed for computer, information processing, communications, and other systems where processor performance or throughput cannot be met satisfactorily with single processors or single cores. For convenience of description, these multiple-processor and multiple-core devices and systems will interchangeably be referred to as multi-core systems or architectures and the terms processors and cores will be used interchangeably. 
     When designing a multicore architecture, one of the most basic decisions that should be made by the designer is whether to use shared data storage or structure (such as is shown in the example in  FIG. 1 ) or private data storage or structure (such as is shown in the example of  FIG. 2 ). 
     In the exemplary shared memory architecture illustrated in  FIG. 1 , each of a plurality of processors  120  is coupled with a single storage or memory subsystem  110  through an arbiter  130  over some bus, communication link, or other connection means  140 . The memory subsystem may be a single memory or some plurality of memories or memory modules that are organized to operate as single logical memory device  110 . 
     In the exemplary architecture illustrated in  FIG. 2 , each of a plurality of processors  220  is separately coupled to its own private memory via connection  230 . The processors are not illustrated as connected to the other processors nor are the memories illustrated as connected to other memories, because such connections are not inherently provided in these private memory architectures. 
     These data storage or structures may commonly be or include a memory, such as but not limited to a solid state memory. Conventionally, the benefit of shared memory is that multiple processors or cores can access it. By comparison, if a private data storage or memory is utilized, then only one processor can see and access it. It may be appreciated however, that even in a shared storage or memory design, although multiple processors or cores can see and ultimately access the shared memory, only one processor or core is allowed access at a time. Some form of memory arbitration must be put in place in order to arbitrate or resolve situations where more than processor or core needs to access shared memory. For processors or cores denied immediate memory access, they must wait their turn, which slows down processing and throughput. 
     Private memory may frequently work well for data that is only required by a single processor or core. This may provide some guarantee of access by the single processor or core with predictable latency. However, many multi-core architectures, particularly architectures of the type including parallel pipeline architectures process a collection of data called a “context”. One example of a parallel pipeline architecture is illustrated in  FIG. 3 . 
     In this architecture, a plurality of blocks  310 , each comprising a memory  320  plus a processor  330 , arranged in parallel groups  340  and sequential sets  350 . Context  360  flows though the blocks as indicated by the arrow  370 , and is successively processed in each sequential set  350 . 
     The context data is usually operated on in turn by various processors  330  in the pipeline. Typically, at any given time, only one processor needs access to or works on or processes the context data, so the context can be stored in private memory for fastest access. But when the processing of the context data by one processor is complete, the processor sends the context to another processor for continued processing. This means that when a private memory or storage architecture is used, the context data must be moved from the private memory of one processor into the private memory of the next processor. This is a specific example of a system problem where copying is required; other system situations may also require such copying, and the scope of the problem being addressed is not intended to be limited to this specific scenario. 
     There are a number of ways to copy the context between private memories in the architecture in  FIG. 3  or other architectures. One of the most straightforward ways is for the processor to execute the copy as shown in  FIG. 4 . 
     In the example approach diagrammed in  FIG. 4 , a contents of memory  400  is copied using the resources of processor  430  which has access to its own private memory  400  and which is granted or in some way acquires access to the private memory  405  of a second processor  435 . This copy path  425  proceeds from memory  400  to memory  405  via the normal communication path between first memory  400  and first processor  430  and between first processor  430  and second memory  405  using a special communication path  415 . It may be noted that second processor  435  may not directly participate in the copy operation, but may operate to provide a permission or to enable access to second memory  405  by first processor  430 . But even this approach requires that the processor spend time away from fundamental program execution with which it is tasked at the time in order to do the private memory to private memory copying operation. This loss of program execution time or machine cycles will usually severely penalize the performance of the system especially when there are sufficient processing tasks at hand and no excess processor capacity or throughput are available. For this copying approach to work, that second memory must be shared between the two processors so that it is visible to the copying processor. This means that the second memory is not really private to the second processor during the copying operation. 
     If some attempt is made to assure that a second memory associated with a second processor really is private, then the data must be placed in some shared holding area or intermediate memory and copied by both processors, that is from the first processor from its first private memory to the share holding area or intermediate memory and then from the intermediate memory by the second processor to its own private memory, as shown in  FIG. 5 . In this example, first processor  540  copies data from its private memory  500  to a holding or intermediate memory  510  and then second processor  590  copies those data from the holding or intermediate memory  510  to its own private memory  520 . The data copy and transfer path  560  is illustrated, as are the first communication path or link  550  between first processor  540  and holding memory  510 , and the second communication path or link  570  between second processor  590  and holding memory  510 . This approach doubles the time or lost processor penalty of having the first and second processors that might otherwise be available to real processing operations, do the copy. 
     An alternative approach that relieves some of this copy operation time is to employ a dedicated Direct Memory Access (DMA) engine to do the actual copying as illustrated in the example of  FIG. 6 . In this approach, first processor  670  is coupled to first private memory  600  over a bus or other communications link  630 , and second processor  690  is coupled to its private memory  620  over a second bus or communications link  680 ; however, these paths are not used for the copy operation. Instead, a Direct Memory Access (DMA) unit, circuit or logic  610  is interposed between the first memory  600  and the second memory  620  and controls the direct transfer of the data between the two memories. First processor  670  acts as the host via connection  640  and provides control over the DMA (and at least its own private memory  600 ) to facilitate the copy or transfer. The transfer or copy path  650  is also shown and is a path from first memory  600  to second memory  620  through DMA  610 . 
     Unfortunately, even this approach has some limitations and is not entirely satisfying. First, DMA  610  requires host control (in this case provided at least in part by first processor  670 ), so the processor still has, for example, to provide the memory source and destination addresses. Because there is no way for first processor  670  to access second memory  620 , processor  670  can use a fixed destination address or processor  690  must communicate a destination address to processor  670  through some communication mechanism. The former solution removes a significant amount of flexibility for second processor  690  since it is not free to assign memory usage in the manner most advantageous to its functioning. The latter requires an explicit coordination between the two processors. 
     Second, the first processor  670 , after having provided the DMA  610  with source and destination addresses and the size of the memory to copy, must wait for the copy operation to be complete in order to free up the occupied memory for new processing data. While less of a penalty than if the processor did the actual copying operation, the wait for completion is still substantial and may usually be unacceptable in high-performance embedded systems. Even if the processor can perform some background task while waiting for the completion, the required bookkeeping adds complexity to the processor program. 
     With reference to  FIG. 7 , a memory segmenting approach is taken. In this approach first processor  780  is coupled to its private memory  700  over a memory to processor bus or link  750 , and second processor  790  is coupled to its private memory  710  over a memory to processor bus or link  770 . Each of first memory  700  and second memory  710  are partitioned into first and second partitions. First processor  780  may continue to communicate and use a first partition  715 , via data path  740  while a second partition  725  is accessible to DMA  720 ; a partition of second memory  710  is also accessible to DMA  720 . DMA  720  may participate in a transfer or copy operation from the second partition of first memory  700 , but there remains some ambiguity regarding copy path  730  as indicated by the question mark “?” in the diagram as to which partition the copied data should be written to. 
     In this way, it is possible to segment memory such that the processor may use one segment while processing its primary data stream using the other partition, while the DMA engine is copying to or from another memory segment, as  FIG. 7  illustrates. This technique is also known as “double buffering”. Unfortunately, neither the upstream processor (e.g. the first processor  780 ) nor the DMA engine  720  can know which memory segment or partition to copy to in the downstream memory (e.g. second memory  710 ) if the memories are private. In addition, if the upstream processor (e.g. first processor  780 ) has a choice of alternative downstream processors to use as the destination, the DMA engine  720  provides no assistance in determining which of those alternative processors would be the proper or best destination. 
     Yet another approach would be to put the code that handles copying into a different thread from the main application code. In systems and devices that have a multi-threading capability, a multi-threaded processor could swap threads during the copy operation and process a different context. However, low-end processing subsystems that are often used in embedded systems do not have multi-threading capability. 
     Therefore it may be appreciated that none of these various approaches provides an entirely suitable solution for copying a specified block of private memory from one processor into a location in the private memory pertaining to a second processor, and that there remains a need for a system for executing such a copy. 
     SUMMARY OF THE INVENTION 
     In one aspect, the invention provides a structured block transfer module, a system architecture, and method for transferring content or data. 
     In another aspect, the invention provides a circuit that allows content in one memory to be shifted or moved to another memory with no direction from a host, the circuit comprising: a connection manager with a plurality of pointer inputs, a plurality of upstream free list pointer outputs, and a plurality of pointer outputs; at least one copy engine with data input busses and data output busses; and a connection between the connection manager and the at least one copy engine. 
     In another aspect, the invention further provides that this circuit may be adapted to perform one or any combinations of these operations: (a) identifying a particular source memory block as the source for a copy operation using any one or more of identified source memory identification criteria; (b) identifying a particular destination memory block as the destination for the copy operation using any one or more of a identified destination memory selection criteria; (c) maintaining a record of available memory blocks and occupied memory blocks for each potential destination processor; and (d) copying or moving the contents of the source memory to the selected destination memory. 
     In another aspect, the invention provides a connection manager with a plurality of pointer inputs, a plurality of upstream free list pointer outputs, and a plurality of pointer outputs. 
     In another aspect, the invention provides a copy engine with data input busses and data output busses. 
     In another aspect, the invention provides a connection means and mechanism for connecting a connection manager and a copy engine. 
     In another aspect, the invention provides a method for transferring the contents of one of a number of blocks of source memory to one of a number of possible destination memories, the method comprising: selecting a source memory; selecting an available destination memory; marking the selected destination as no longer available; copying the contents of the selected source memory into the selected destination memory; and marking the selected source as available. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a prior-art configuration with all processors using one common memory. 
         FIG. 2  shows a prior-art configuration with each processor having a private memory. 
         FIG. 3  shows a prior-art parallel pipeline structure with a context that moves through the pipeline as it is processed. 
         FIG. 4  shows a prior-art configuration where a processor copies the contents of its memory to the memory of the succeeding processor. 
         FIG. 5  shows a similar configuration to the configuration in  FIG. 4 , but with a shared “holding” memory between the two processors. 
         FIG. 6  shows a prior-art configuration where a DMA engine or processor copies the contents between the memories of two processors, under the direction of the sending processor. 
         FIG. 7  shows what might be attempted using segmented memories with a DMA copying between them. 
         FIG. 8  shows an exemplary embodiment of an aspect of the invention. 
         FIG. 9  shows a possible usage or application of an embodiment of the invention. 
         FIG. 10  shows an embodiment of a processing unit as depicted in  FIG. 9 . 
         FIG. 11  shows another exemplary embodiment of the invention. 
         FIG. 12  is a diagrammatic flow-chart depicting a possible exemplary process for implementing a structured block copy using an embodiment of the invention. 
         FIG. 13  illustrates an exemplary availability qualifier that may be used in an embodiment of the invention. 
         FIG. 14  shows one embodiment of the inventive availability qualifier of  FIG. 13 . 
         FIG. 15  shows another embodiment of the availability qualifier of  FIG. 13 . 
         FIG. 16  shows an embodiment of the availability qualifier of  FIG. 13  that ensures that no source queue goes for too long a period of time without being selected. 
         FIG. 17  shows one exemplary means and process of altering data during the copy process using a replacement engine. 
         FIG. 18  shows one exemplary embodiment of the Replacement Engine illustrated in  FIG. 17 . 
         FIG. 19  shows one embodiment of the Replacement Module and replacement engine shown in  FIG. 18 . 
         FIG. 20  shows a possible process for implementing replacement using the Replacement Module embodiment illustrated in  FIG. 19 . 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS OF THE INVENTION 
     Various aspects, features, and embodiments of the invention are now described relative to the figures. 
     In one aspect, the invention provides a structure for a Structured Block Transfer Module (SBTM) block or circuit, such as shown in the embodiment of  FIG. 8 . This embodiment of the SBTM as illustrated has been implemented using a Field Programmable Gate Array (FPGA), but the technology used for realizing the circuits described is not critical to the invention. Alternatively, it could have been implemented in an Application Specific Integrated Circuit (ASIC) or custom integrated circuit or combination of integrated circuits. 
     The exemplary SBTM  800  includes a connection manager  805  and one or more copy engines  840 . The number of copy engines is not critical to the invention. Connection manager  805  receives copy requests on pointer inputs  810 , selects copy requests based on a criterion or criteria that is/are not critical to the invention, selects a copy destination based on a criterion or criteria that is/are not critical to the invention, selects one of the copy engines  840  based on a criterion or criteria that is/are not critical to the invention, and instructs the selected copy engine  840  via copy enable signal  820  to copy the data from the selected source via copy input bus  835  to the selected destination via copy output bus  845 . Free list inputs  825  provide a selection of available memory locations for copy destinations. Selection of a copy engine  840  only occurs if there is more than one copy engine  840  present. The format of copy enable signal  820  and the method of instruction are not critical to the invention. Copy enable signal  820  could be implemented using a collection of inputs, one for each copy engine  840 , or by a common bus with an instruction identifying the targeted copy engine  840 , or by any other suitable means. After copying is complete, connection manager  805  informs the selected destination of the location of the copied data via one of pointer outputs  815 . 
     Connection manager  805  also places the pointer value on the selected pointer input  810  onto the upstream free list output  850  for the selected source. The number of pointer inputs  810 , copy inputs  835 , and upstream free list outputs  850  is determined by the number of potential sources of data to be copied. Each such source contributes a pointer input  810 , a copy input  835 , and an upstream free list output  850 . The number of pointer outputs  815  copy outputs  845 , and free list inputs  825  is determined by the number of potential copy destinations. Each destination contributes a pointer output  815 , a copy output  845 , and a free list input  825 . The format (signal, bus, serial connection, etc.) of pointer inputs  810 , pointer outputs  815 , and upstream free list outputs  850 , and free list inputs  825  may vary and is not critical to the invention. If the number of copy engines is different from the number of sources and/or destinations, then bussing, switching, or other well-understood methods can be used to connect the copy engines to the source and destination busses. 
     For the exemplary SBTM, given a number of potential source memory locations to be copied, the SBTM can provide any one or any combination of two or more of the following capabilities and features: 
     (1) Identify a suitable source memory as the source for a copy operation using any one or more of a number of criteria such as by way of example but not limitation, load balancing, and/or memory availability. 
     (2) Identify a suitable memory block as the destination using any one or more of a number of criteria such as by way of example but not limitation, specific direction, load balancing, and/or memory availability. 
     (3) Maintain a record of available and occupied memory blocks for each potential destination processor. 
     (4) Copy the contents of the selected source to the selected destination. 
     (5) Alter selected portions of the data during the copy process. 
     (6) Execute multiple block copies concurrently. 
     (7) Communicate back to the prior (upstream) SBTM (see  FIG. 9 ) after the copy to inform the prior (upstream) SBTM in the pipeline that the source memory block is no longer being used. 
     (8) Receive communication from the subsequent (downstream) SBTM that it has emptied a memory block and mark that block as now being available for re-use. 
     As used herein, the term copy may mean copying or duplicating a content from one memory or storage location to another, or it may be moving or shifting the contents from one storage or memory location to another location without retaining the contents at the original storage or memory location, or it may mean realizing a content or data at a second storage or memory location without caring if the content or data was retained or deleted from the first storage or memory location. 
     These SBTM  800  can be arranged with processing elements as shown in the exemplary pipeline segment Configuration  900  of  FIG. 9 . 
     In this pipeline segment configuration  900 , at least one processing unit  920  may be coupled with at least two SBTMs  905  by SBTM data output  930 , SBTM pointer output  950 , SBTM data input  940 , and SBTM pointer input  960 . Each SBTM  905  may be further coupled with an upstream SBTM via free list connection  910 . 
     As illustrated in exemplary drawing  FIG. 9  the system may comprise multiple SBTMs, each copying into a Processing Unit  920 , and following each other such that the destination for one SBTM becomes the source for the next SBTM. In this configuration, with respect to a given Processing Unit  920 , the SBTM for which the Processing Unit acts as a destination may be considered an upstream SBTM; the SBTM for which the Processing Unit acts as a source may be considered a downstream SBTM. In the specific example of  FIG. 9 , with respect to specific Processing Unit  920 , SBTM  905  is the upstream SBTM, and SBTM  970  is the downstream SBTM for data flowing from left to right. 
     Comparing the structures illustrated in  FIG. 8  and  FIG. 9 , SBTM data output  930  in  FIG. 9  may correspond to SBTM data output  845  in  FIG. 8 ; SBTM pointer output  950  corresponds to SBTM pointer output  815 ; SBTM data input  940  may correspond to SBTM data input  835 ; SBTM pointer input  960  may correspond to SBTM pointer input  810 ; and free list connection  910  may correspond to free list output  850  with respect to SBTM  970 , and may correspond to free list input  825  with respect to SBTM  905 . 
     Processing unit  920  is illustrated in exemplary embodiment of  FIG. 10 . In this illustration, processing unit  1000  includes a processor  1030  connected to a memory  1020  by a memory bus  1010  which may advantageously be a dedicated memory bus. The processor may also be connected to a queue  1090 , wherein the queue input  1040  may correspond to SBTM pointer output  950  in the embodiment of  FIG. 9 . The output  1050  of processor  1030  may correspond to SBTM pointer input  960 . In the configuration of  FIG. 10 , memory  1020  may advantageously be a dual-port memory; the second port may be connected to arbiter  1060 . Arbiter  1060  provides access to memory  1020  for data busses  1070  and  1080 . Arbiter  1060  may provide access to other busses as well, but those bus accesses (if any) are not critical to the invention. Memory bus  1070  corresponds to SBTM data output  930 , and memory bus  1080  corresponds to SBTM data input  940 . The various memory busses and the arbiter may use standard memory access techniques well-known to those skilled in the art or to be developed in the future, and are not critical to the invention, and are therefore not described in greater detail herein. 
       FIG. 11  is an illustration showing a non-limiting exemplary embodiment of one aspect of the invention, represented as configuration  1100 . Data, such as memory data, may be transferred from one of several sources  1115  to one of several destinations  1125  via a connection established by Connection Manager  1105 . The decision regarding which source and which destination to use for a particular connection may be made by Connection Manager  1105 . Upon deciding on a connection—that is a source and a destination pair, Connection Manager  1105  instructs Copy Engine  1180  via connection  1190  to begin the copy operation between the selected source and destination. The instruction to the Copy Engine  1180  may be in the form of a signal value, command on a bus, or any other suitable mechanism or message. The memories from which data is copied and to which data is copied may be of varying or fixed size. The size of the memory is not critical to the invention. The location of the memories is also not critical to the invention. Some or all of the memories may reside in the same or different integrated circuits. In the one embodiment, Block Random Access Memory (BRAM) is used inside an FPGA, but external memories could have been used instead, and mixed configurations using internal and external memories may be implemented. 
     In the illustrated embodiment, Connection Manager  1105  has a plurality of pointer inputs  1120  and pointer output  1110  that are connected to a corresponding plurality of sources  1115 . Connection Manager  1105  may also have a plurality of pointer outputs  1145  that connect to a corresponding plurality of destinations  1125 . Connection Manager  1105  may also have a plurality of pointer inputs  1130  that connect to Free List  1135 . Each Free List  1135  includes an input  1190  from a destination  1125 . A control signal line or set of lines or interface  1140  may also be provided between the connection manager  1105  and the copy engine  1180  that provides a way for Connection Manager  1105  to control Copy Engine  1180 . Copy Engine  1180  has a plurality of outputs  1170  to a corresponding plurality of Destinations  1125 . The specific nature of connections  1110 ,  1120 ,  1130 ,  1140 ,  1150 ,  1160 , and  1170  is not critical, and can be implemented in any number of ways well known to those skilled in the art. The number of Sources  1115  is at least one; the number of Destinations  1125  is at least one; and the number of Sources  1115  need not equal the number of Destinations  1125 . 
     In the case where there is more than one Copy Engine  1180 , the connections shown can be replicated for each Copy Engine  1180 . Alternatively a Copy Engine  1180  could be associated with each Source  1115  with one set of dedicated connections between each Source  1115 /Copy Engine  1180  pair. Alternatively a Copy Engine  1180  could be associated with each Destination  1125  with one set of dedicated connections between each Destination  1125 /Copy Engine  1180  pair. 
     Free List  1135  can contain a list of destination memory blocks that are available to receive data. Input  1140  feeds Free List  1135  and can add pointers of available memory blocks to Free List  1135  as those blocks are freed up by a downstream SBTM. Pointer output  1110  can feed the Free List of an upstream SBTM. Input  1120  can provide the location of the block of data to be copied. Output  1160  provides a pointer to the block of data that has been copied to the destination. The specific implementation of Free List  1135  is not critical to the invention. In the preferred embodiment, it has been implemented using a queue, and specifically, a Fast Simplex Link (FSL), which is a means of implementing a queue known to users of certain Field Programmable Gate Arrays (FPGAs). 
     It may be appreciated that this connectivity permits the connection or coupling of any source  1115  with any destination  1125  under the control of Connection Manager  1105  and as a result of these connections, provides an ability to copy data or other content or information between any of the sources and destinations. Any processor may be a source or a destination for a given copy operation, depending upon how the system is configured. It should be appreciated that the number of Copy Engines  1180  need not be the same as either the number of Sources or the number of Destinations. 
       FIG. 12  is a diagrammatic flow chart illustrating an embodiment for a procedure or process for transferring a structured block of data from a source to a destination. The process or procedure may advantageously use a Structured Block Descriptor or may use other descriptor. Although certain non-limiting embodiments of the invention may utilize particular structured block descriptors, the specific structure is not critical to the application. Advantageously, whatever structure is utilized, it will advantageously describe basic information about the block being copied and its location. In the preferred embodiment, it may include or consist simply of an address. 
     Connection Manager  1105  firsts selects (step  1200 ) a source  1115 . It then selects (step  1210 ) a destination  1125 . The order of selection is not important and may be reversed or the selections may be concurrent. Once the source and destination have been selected, the next Structured Block Descriptor on Free List  1135  corresponding to the selected destination is removed (step  1220 ) from its Free List  1135  and held by the Connection Manager  1105 . Connection Manager  1105  then instructs (step  1230 ) Copy Engine  1180  to copy (step  1240 ) the contents from data input bus  1150  corresponding to the selected source to data output bus  1170  corresponding to the selected destination  1125 . If multiple Copy Engines  1180  are used and there is not a direct correspondence between each Copy Engine  1180  and either a Source  1115  or Destination  1125 , then in addition to selecting a Source  1115  and a Destination  1125 , a Copy Engine  1180  must also be selected. 
     The means of copying, moving, duplicating, or shifting may be any of the means or methods known to one skilled in the art. One non-limiting but advantageous embodiment uses a Direct&#39; Memory Access (DMA) copy means and method. During the copying process, selected portions of the data may optionally be altered en route so that the data at the destination may optionally be an altered version of the data from the source. Once the copying is complete, the Structured Block Descriptor that was previously removed (step  1220 ) from the Free List is sent (step  1250 ) to the selected destination  1125  on pointer output  1145 . The Structured Block Descriptor at the selected source  1115  is taken from the source via pointer input  1120  and sent (step  1260 ) to output  1110  corresponding to the selected source  1115 . 
       FIG. 12  describes an SBTM  905  that is taking data from an upstream source  1115  and transferring it to a downstream destination  1125 . Step  1260  of that process includes the sending of a Structured Block Descriptor to the upstream Free List  1135 . For the upstream SBTM  905 , this makes available the memory block that was just emptied; by putting that block back on the Free List  1135 , it can now be allocated to a new block by the upstream SBTM  905  (step  1220 ). 
     There are a variety of means which can be used to select a source  1115  and destination  1125 . Among the possible means for selecting source and destination are included queue depth and memory availability, alone or combined with round-robin or other such arbitration schemes. An additional means is available for selecting the destination  1125 , which is referred to as Direct Routing. In this Direct Routing case, the Structured Block Descriptor includes an index number or some other identifier specifying a destination  1125 , and the Connection Manager  1105  ensures that the specified destination  1125  is selected. 
     One non-limiting but preferred embodiment uses a non-obvious combination of queue depth and memory availability by creating a composite measure as shown in the embodiment of  FIG. 13 . 
     With reference to  FIG. 13 , a composite signal  1330  is created without serially making decisions regarding memory availability and then task queue depth. An availability signal (Available)  1300  and Queue Depth signal  1310  are provided to Availability Qualifier block  1320 , which creates the Composite signal  1330  that includes signal contributions from the Availability and Queue Depth inputs. The particular means of qualifying the queue depth with availability can vary and are not critical to the invention. Two exemplary embodiments showing non-limiting alternative means are shown and described relative to the embodiments in  FIG. 14  and  FIG. 15 . 
     In the embodiment illustrated in  FIG. 14  Queue Depth signal  1410  is an N-bit value. Availability signal  1400  is concatenated with the queue depth signal  1410  as the new Most Significant Bit (MSB) to provide Composite signal  1420  as an N+1-bit signal. If the Available signal  1400  is asserted as a logical “1” (or high signal), then the resulting N+1-bit Composite signal value will always be higher value than any Composite signal having the Available signal unasserted as a logical “0” (or low signal) since that bit is the MSB of the composite signal  1420 . Given a plurality of Source queues utilizing this methodology, the selection will be made by selecting the Source queue with the highest value for the resulting n+1-bit number. If a particular implementation has an Available signal that asserts as a 0 instead of a 1, that signal would need to be inverted before being presented to the circuit of  FIG. 14 . Therefore, it will be appreciated that various different or opposite signaling logic schemes may be utilized without deviating from the invention. 
       FIG. 15  shows an alternative non-limiting embodiment of Availability Qualifier  1320  of  FIG. 13 . Here each bit of N-bit Queue Depth signal  1510  is logically ANDed with Available signal  1500  through a plurality of AND gates  1520 . Alternative logic circuits that result in the logical ANDing operations or equivalent may be used. If the Available signal is asserted as a 1, then the resulting Composite signal  1530  will be equivalent in value to the original Queue Depth signal  1510 . If the Available signal is unasserted as a 0, then the resulting value will be 0, which is guaranteed to be the lowest Composite value. Given a plurality of Source queues utilizing this methodology, in at least one non-limiting embodiment, the selection will be made by selecting the Source queue with the highest value for the resulting n+1-bit number. If a particular implementation has an Available signal that asserts as a logical 0 instead of a logical 1, that signal would need to be inverted before being presented to the circuit of  FIG. 15 . Again, in this alternative embodiment, it will be appreciated that various different or opposite signaling logic schemes may be utilized without deviating from the invention. 
     The preceding discussion allows the selection of the available queue with the greatest depth. This is appropriate when selecting an input from which to load-balance, since the goal is to unburden the fullest queue. However, when load balancing to an output, the intent is to pick the emptiest queue. Similar circuits can be used to achieve this, the difference being that the Availability signal is inverted in both circuits, and in the case of the latter circuit, the AND gates are replaced by OR gates. The selection process in either case is to select the queue with the lowest composite value. In these exemplary embodiments, it will be appreciated that various different or opposite signaling logic schemes may be utilized without deviating from the invention. 
     Yet another embodiment may alternatively be utilized and which can ensure that no Source Queue remains unselected for an extended period of time.  FIG. 16  shows a non-limiting embodiment similar to that of  FIG. 15 , but which includes an additional Counter  1640 . The counter has a pre-defined threshold, signal  1650  which is communicated to a plurality of logical OR gates (or equivalent logic). That threshold signal  1650  is then logically ORed with the qualified queue depth value  1610  using logic OR gates  1660  to generate a final Composite signal  1630 . When the threshold is reached, signal  1650  will assert 1, and all bits of Composite signal  1630  will be 1, ensuring that this value will be the maximum value, prioritizing this signal for selection. Once selected, Counter  1640  is reset using signal  1670 , and threshold signal  1650  will be deasserted. Given a plurality of Source queues utilizing this methodology, in at least one non-limiting embodiment, the selection will be made by selecting the Source queue with the highest value for the resulting n+1-bit number. 
     Copied data may optionally be altered during the copying process or operation. There are a number of means by which the copied data can be altered or undergo additional processing during the copy process; the means by which this processing is accomplished or the processing performed is not critical to the invention. In one non-limiting embodiment, a Direct Memory Access (DMA) engine may be used to provide the desired copy operation.  FIG. 17  shows one DMA engine based embodiment. DMA engine  1720  acquires data from Data Source  1700  using source address line  1710 . Data line  1740  from Data Source  1700  may not go directly to DMA  1720 , but may optionally go first through Replacement Engine  1750 . Replacement engine  1750  is responsible for replacing portions of the data being copied with new data and may be implemented in any one or combination of ways. Altered data emerges from the replacement engine on data line  1760 , and is placed into Data Sink  1730  by DMA  1720  using address line  1780  and data line  1770 . 
     The specific workings of Replacement Engine  1750  may be implemented in a variety of ways and the specific way or means is not critical to the invention.  FIG. 18  shows one non-limiting embodiment of Replacement Engine  1750 . It includes a port or other means for receiving an original data signal  1800  and at least one and advantageously a plurality or a series of Replacement Modules  1860 . The number of Replacement Modules can vary (for example, depending on the specific application or intended functionality) and is not critical to the invention. Typically, the number and character of the replacement modules are determined or selected on the basis of the number of blocks of data that need replacing, and the replacement data. The or each Replacement Module  1860  has two outputs, a Replace signal  1870  and a New Value signal  1820 . The original data  1800  is logically ANDed with the inverse of all the Replace signals  1870  using AND gate  1810 . The output of this AND gate will be deasserted 0 if any Replace signal  1870  is asserted 1. If no Replace signal  1870  is asserted 1, then the output of AND gate  1810  will be the same as original data  1800 . 
     The two outputs  1870  and  1820  of each Replacement Module  1860  are logically ANDed together using AND gate  1830 . If Replace signal  1870  for a given Replacement Module  1860  is deasserted 0, then the output of the corresponding AND gate  1830  will be deasserted 0. If the Replace signal  1870  for a given Replacement Module  1860  is asserted 1, then the output of the corresponding AND gate  1830  will be the same as the value of the corresponding New Data value  1820 . If all of the Replacement Modules are designed with non-overlapping replacement criteria, then zero or one Replacement Module will have its Replace signal  1870  asserted 1. As a result, only one of the AND gates  1810  and  1830  will have a non-zero value. The outputs of all of the AND gates  1810  and  1830  are logically ORed together using OR gate  1840 . If any Replace signal is asserted 1, then output  1850  will be the same as the New Data signal  1820  corresponding to the asserted Replace signal. If no Replace signal is asserted 1, then output  1850  will be the same as the original data. 
     It can be appreciated that the effect of this replacement is to modify select portions (or even all portions) of the data being copied in a manner specific to the intent of a particular use. Such replacement may or may not be required in a given use, but the capability constitutes an optional aspect of the invention. Other implementations can be used, with arbitration capabilities in the case of overlapping replacement criteria, using techniques known to one skilled in the art in light of the description provided here. 
     A non-limiting embodiment of Replacement Module  1860  is illustrated in  FIG. 19 . Multiplexer  1910  selects between original data signal  1900  and a value from New Value Loader  1920 . New Value Loader  1920  receives its value from New Value Register  1930 . How New Value Register  1930  receives its value is not critical to the invention. It could be initialized upon system initialization, it could have a permanent hard value assigned, or some other means of loading the value could be used. Likewise, Start Counter  1950  and Length Counter  1960  have a threshold values that could be initialized, be hard-wired, or be assigned by some other means. 
     The functioning of the example Replacement Module circuit in  FIG. 19  is illustrated in the embodiment of  FIG. 20 . Replace Controller  1940  sets (step  2005 ) the selector  1945  for Multiplexer  1910  such that the original unaltered data on signal  1900  passes through to output  1915 . Both counters  1950  and  1960  are reset (step  2010 ). New Value Loader  1920  is loaded (step  2015 ) from New Value Register  1930 . The order in which Steps  2010  and  2015  occur is not important; they could also be executed simultaneously. Start Counter  1950  is started (step  2020 ). When the threshold is reached (step  2025 ), Replace Controller  1940  changes (step  2030 ) the selector  1945  value for Multiplexer  1910  to pass data from New Value Loader  1920  on signal  1925  out onto output  1915 . Length Counter  1960  starts counting (step  2035 ), and at each cycle New Value Loader shifts (Step  2040 ) the next piece of data into Multiplexer  1910 . Note that this could be single-bit data, byte data, or any other data quantum. The number of bits transferred at once is not critical to the invention. Length Counter  1960  is incremented (Step  2055 ), and once the threshold for Length Counter  1960  is reached (Step  2045 ), Replace Controller  1940  sets (step  2050 ) the selector  1945  value for Multiplexer  1910  to pass the original unaltered data from signal  1900 . The format of signals  1900 ,  1915 , and  1925  could be any format suitable for passing the format of data chosen, including busses of different widths. The format of these signals is not critical to the invention. 
       FIG. 17 ,  FIG. 18 ,  FIG. 19 , and  FIG. 20  illustrate non-limiting but exemplary logic and circuit means of replacing data. Other suitable means as may be known in the art may alternatively also be used in conjunction with the invention. Other types of data replacement can be used as well. The above structure and method rely on replacing data at a fixed point in a data stream. Alternatively, pattern-matching techniques may be used to identify strings of data and replace them with other strings of data. The specific means or procedures of determining which data to replace and of deciding which data to use as replacement are not critical to the invention and may be dependent on factors such as specific circuit application, desired complexity and cost of the implementation, or other factors alone or in combination. 
     ADDITIONAL DESCRIPTION 
     As used herein, the term “embodiment” means an embodiment that serves to illustrate by way of example but not limitation. 
     It will be appreciated to those skilled in the art that the preceding examples and preferred embodiments are exemplary and not limiting to the scope of the present invention. It is intended that all permutations, enhancements, equivalents, and improvements thereto that are apparent to those skilled in the art upon a reading of the specification and a study of the drawings are included within the true spirit and scope of the present invention.