Flow control mechanisms for avoidance of retries and/or deadlocks in an interconnect

BACKGROUND

p-00021. Field

p-0003This disclosure relates generally to data processing systems, and more specifically, to flow control mechanisms in a coherency interconnect.

p-00042. Related Art

p-0005Increasingly complex on-chip interconnect micro-architectures have been developed, in part, to achieve higher data transfer bandwidths and/or lower latencies in system on a chip (SoC) designs. Typically, interconnect fabrics in accord with such micro-architectures seek to provide multi-path, point-to-point communications between a large and scalable set of processor cores, memory controllers, caches, direct memory access (DMA) controllers, bridges, etc. Coherency management techniques are employed to present a coherent system memory state while allowing multiple in-flight interconnect transactions to proceed concurrently in accordance with some appropriate total ordering of transactions. Basic storage operations such as reading or writing of storage locations, synchronization, etc. may be implemented using multiple transactions between two or more end-point devices.

p-0006As is well understood in the art, coherency in a multiprocessor system can involve complicated interactions between processor cores, their cache hierarchies and other devices. These interactions typically involve flows of interdependent transactions between entities. In some interconnect designs, particularly those that include a point-to-point interconnect matrix or pipelined busses, large numbers of in-flight transactions may share and compete for interconnect resources. In general, competition amongst transactions that are themselves subject to dependencies can create opportunities for deadlock. Although an impending deadlock can, in practice, often be avoided using retry techniques, frequent retries tend to sap system performance and, in any case, create scenarios that can be very hard to debug.

p-0007Techniques are desired to eliminate retries or at least avoid particular situations in which retries might otherwise be employed in a coherency interconnect.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example and not limitation with reference to the accompanying figures, in which like references generally indicate similar elements or features.

<figref idrefs="DRAWINGS">FIG. 1</figref> is a block diagram of a computational system in which a coherency interconnect supports flow control mechanisms in accordance with some embodiments of the present invention.

<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram that illustrates, with emphasis on an exemplary address transaction, links and sub-links between various devices of a computational system that employs a coherency interconnect in accordance with some embodiments of the present invention.

<figref idrefs="DRAWINGS">FIG. 3</figref> is a dependency graph that illustrates dependencies amongst constituent transactions of various illustrative operations in a coherency interconnect together with an illustrative assignment of class of transaction (CoT) labels to constituent transactions.

<figref idrefs="DRAWINGS">FIG. 4</figref> is a combined block diagram and flow chart illustrating use of a class of transaction (CoT) denominated request-grant protocol employed in some embodiments of the present invention.

<figref idrefs="DRAWINGS">FIG. 5</figref> is a block diagram that illustrates address transaction ordering in an address path portion of a coherency interconnect in accordance with some embodiments of the present invention.

<figref idrefs="DRAWINGS">FIG. 6</figref> is a block diagram that illustrates, with emphasis on an exemplary data transaction, links and sub-links between various devices of a computational system that employs a coherency interconnect in accordance with some embodiments of the present invention.

p-0015Skilled artisans will appreciate that elements or features in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions or prominence of some of the illustrated elements or features may be exaggerated relative to other elements or features in an effort to help to improve understanding of embodiments of the present invention.

DETAILED DESCRIPTION

p-0016Flow control mechanisms have been developed to avoid, and in some situations or embodiments eliminate, retries of transactions in a coherency interconnect. In particular, a class of transaction (CoT) framework is defined whereby individual transactions are associated with CoT labels consistent with chains of dependencies that exist between transactions initiated by any of the cooperating devices (e.g., processors, targets and interveners) that participate in a given operation. In general, it will be understood that coherency protocols create dependencies that, when mapped to physical resources, can result in cycles in a graph of dependencies and deadlock. To support architectural mechanisms for deadlock avoidance, CoT labels are applied to individual transactions consistent with a precedence order of those transactions both (i) with respect to the operations of which such transactions are constituent parts and (ii) as amongst the set of such operations supported in the coherency interconnect. Taken together, the CoT labels applied to respective transactions constitute a CoT framework that may be used by coherency managers to efficiently support concurrent in-flight transactions without retry.

p-0017CoT-denominated request-and-grant protocols are used in some embodiments of the present invention to ensure that dependency chains remain acyclic even when accounting for the potentially competing resource requirements of multiple in-flight operations and their constituent transactions. In some embodiments, request-and-grant mechanisms are employed for address-type transactions that are the initiating transaction constituents of storage-oriented operations supported within a coherency domain, e.g., load operations, store operations, data cache flush operations, translation lookaside buffer (TLB) synchronize operations, etc. For example, a CoT framework that reflects a particular transaction precedence order and an explicit CoT denominated request/grant protocol used for an initiating address-type transaction may be leveraged to ensure that dependency chains remain acyclic. In this way, availability of interconnect resources for all possible successor transactions of any in-flight transaction may be assured. In some embodiments, such assurance may be provided by checking, for a given request (by an initiating device) for a transaction with an associated CoT label of N, where 0≦N≦MAX_CoT-1, to ensure that sufficient unallocated interconnect resources exist to complete at least one transaction of each higher class, M, where N&lt;M≦MAX_CoT-1. An implementation may then grant a CoT-denominated transaction request for which resources are available notwithstanding resource requirements of in-flight operations and their constituent transactions (i.e., transactions in flight, together with their possible successor transactions). The grant supplied to the requesting device is itself CoT-denominated and signals unconditional availability of resources (e.g., a buffer) for a transaction of class N. Transactions for which grants are supplied may be initiated by respective requesting devices and are processed in accord with any total ordering imposed by the coherency interconnect.

p-0018Depending on the implementation of the coherency interconnect and/or other design factors, CoT-denominated request-and-grant protocols may (or may not) be needed (or used) for other types of transactions. For example, in some embodiments in which sufficient dedicated resources, such as for target and/or coherence responses, can be assured as a matter of architecture or design, transactions requiring such resources may be initiated (as successors to a corresponding addresses-type transaction) without additional CoT-denominated request/grant interactions. Similarly, in some embodiments, a fixed number of successor data transactions (e.g., a single data transaction) follow(s) an initiating address transaction and, as a result, the decision to grant the corresponding device request itself provides a sufficient gating decision point to assure resource availability. Accordingly, in embodiments in which sufficient data path resources may be guaranteed a priori, data transactions may also omit CoT-denominated request/grant interactions.

p-0019Note that, notwithstanding the foregoing, for embodiments or interconnect topologies that do or may commingle transactions of multiple types in a given channel (e.g., in a serial bus), omission for non-address-type transactions may not be appropriate. In general, use for any given transaction or transaction type of CoT-denominated request/grant interactions is implementation specific. Nonetheless, for purposes of illustration with respect to certain exemplary embodiments and without limitation, the description herein assumes that address-type transactions employ CoT-denominated request/grant protocols, that address response-type transactions (including target and coherence responses) do not employ CoT-denominated request/grant protocols, and that data-type transactions employ CoT-denominated request/grant protocols optionally with respect to operations for which multiple successive data-type transactions (from a single target) may be employed.

p-0020For concreteness of description, we focus on certain illustrative implementations of a coherency interconnect in a computational system with multiple processors, caches, memory controllers, input/output (I/O) bridges, etc. Typically, the coherency interconnect presents bus-type interfaces to a scalable on-chip interconnect fabric that itself employs point-to-point interconnects, crossbars, pipelined buses and/or any other interconnect technologies suitable for the concurrent multipath interconnectivity desired in a particular implementation. In some embodiments, separate paths are provided for different types of transactions, e.g., for address transactions, address response transactions and data transactions. In some embodiments, a coherency domain may span multiple levels of interconnect and/or multiple chips or multichip modules. In general, illustrative implementations described herein include support for a range of variations in form, scalability and features of the coherency interconnect that need not be included in all embodiments. Accordingly, based on the description herein and without limitation, persons of ordinary skill in the art will appreciate applications of the invented techniques to other interconnects and to other computational systems.

p-0021For generality, the illustrated implementations are described in a manner that is generally agnostic to design details such as instruction set architecture, I/O device types, operating system conventions, memory and/or coherence models, interconnect technology, communication or data transfer protocols and interfaces employed. Where useful to provide concreteness of description, certain illustrative designs are described, though generally without limitation. Techniques described herein have broad applicability to other interconnects, topologies and computational system designs, but will be understood and appreciated by persons of ordinary skill in the art in the illustrated context. Accordingly, in view of the foregoing and without limitation on the range of interconnects, processor or system architectures, interfaces and coherency domains that may be employed in embodiments of the present invention, we describe certain illustrative embodiments.

h-0004System and Integrated Circuit Realizations, Generally

p-0022<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates a computational system <b>100</b> in which devices such as processors <b>101</b>, memory subsystems (e.g., lookaside cache(s) <b>105</b>, memory controllers <b>106</b> and any associated caches (e.g., caches <b>15</b>) and memory <b>102</b>, <b>12</b>) and I/O facilities (e.g., host bridge <b>110</b> and the I/O devices <b>103</b> to which it interconnects) are operatively coupled via a coherency interconnect <b>104</b>. In the illustrated configuration, coherency interconnect <b>104</b> includes a scalable on-chip network that is suitable for interconnecting multiple processor cores with memory and I/O subsystems. Processors <b>101</b> are linked to each other, to memory <b>102</b>, <b>12</b> and host bridges <b>110</b> via the coherency interconnect <b>104</b>. In some embodiments, coherency interconnect <b>104</b> implements a modern front-side multi-path interconnect fabric that supports concurrent non-conflicting transactions and high data rates. Illustrated processors, memory subsystems and I/O facilities, as well as the general character of operations thereamongst, are of any suitable or conventional design.

p-0023As a general matter, any of a variety of memory designs and hierarchies may be employed in, or in conjunction with, embodiments of the present invention. Accordingly, <figref idrefs="DRAWINGS">FIG. 1</figref> illustrates a superset of caches and memory subsystems that may be implemented in any particular computational system. In particular, the illustrated collection of caches and memory subsystems need not be implemented in all embodiments or, indeed, in any particular embodiment. Rather, <figref idrefs="DRAWINGS">FIG. 1</figref> illustrates a collection of caches and memory subsystems that may be employed in range of designs, including those with backside L2 (processor-associated) caches <b>11</b> and those with standalone or lookaside caches <b>15</b> that represent state that spans the data and/or instruction spaces of multiple processors <b>101</b>. In some embodiments, memory controllers <b>16</b> interface directly with coherency interconnect <b>104</b> and memory (e.g., memory <b>12</b>). In some embodiments, at least some level of cache <b>105</b> is interposed between interconnect <b>104</b> and memory (e.g., memory <b>102</b> and associated memory controllers <b>106</b>). For example, in some embodiments, caches <b>105</b> are configured as L3 cache and represent state that spans the data and instruction spaces of processors <b>101</b>, while additional levels of L1 cache (not specifically shown) and L2 cache (e.g., cache(s) <b>11</b>) are collocated with individual processors or processor cores.

p-0024Whatever the collection of caches and memory subsystems implemented in a given design, their operation, together with coherency interconnect <b>104</b>, will be understood to relative to a coherency domain. In some embodiments consistent with the illustration of <figref idrefs="DRAWINGS">FIG. 1</figref>, a coherency domain <b>124</b> spans a collection of memory subsystems including memory <b>102</b>, <b>12</b> and caches (e.g., the illustrated L2/L3 caches <b>11</b>, <b>105</b> and any other caches or lookaside stores), processors <b>101</b>, interconnect <b>104</b>, and I/O host bridges <b>110</b> that cooperate through relevant protocols to meet memory coherence, consistency, ordering, and caching rules specific to a platform architecture. For example, in some embodiments, coherency domain <b>124</b> conforms to coherence, consistency and caching rules specified by Power Architecture® technology standards as well as transaction ordering rules and access protocols employed in a CoreNet™ interconnect fabric. The Power Architecture and Power.org word marks and the Power and Power.org logos and related marks are trademarks and service marks licensed by Power.org. Power Architecture® technology standards refers generally to technologies related to an instruction set architecture originated by IBM, Motorola (now Freescale Semiconductor) and Apple Computer. CoreNet is a trademark of Freescale Semiconductor, Inc.

p-0025Memory addresses can be, and typically are, used to identify storage locations within (or from the perspective of) coherency domain <b>124</b>. In some cases, a system memory portion of this coherency domain address space is used to address locations in memory <b>102</b>, <b>12</b>, while a peripheral memory portion of the coherency domain address space is used for addresses that processors <b>101</b> view as assigned to I/O host bridges <b>110</b>. Using facilities of an I/O memory management unit (IOMMU), the I/O host bridge translates between coherency domain addresses and addresses (or identifiers) for particular I/O devices within a corresponding I/O domain (e.g., I/O domain <b>123</b>).

p-0026In general, cooperation amongst devices (e.g., amongst the processors, memory subsystems and I/O facilities illustrated in <figref idrefs="DRAWINGS">FIG. 1</figref>) is via coherency interconnect <b>104</b> and will be understood in the context of storage operations initiated by some of the devices (typically, processors <b>101</b> and I/O bridge <b>110</b>) relative to addressable locations in target devices (typically, memory <b>101</b>, <b>12</b>, I/O Bridge <b>110</b> and/or the I/O devices <b>103</b> to which I/O Bridge <b>110</b> interconnects). For simplicity though without limitation, much of the description herein focuses on storage operations initiated by one of the processors <b>101</b> relative to addressable locations in memory <b>102</b> with possible intervention (based on cache coherence considerations) by another processor <b>101</b>. Based on the description herein, persons of ordinary skill in the art will also appreciate operations and interactions consistent with other initiators, targets, memory hierarchies and topologies.

p-0027Coherency interconnect <b>104</b> supports individual storage operations using sets of constituent transactions that convey atomic units of information between devices. For example, in some embodiments, storage operations are effectuated using a series of separate address transactions, address-response transactions and/or data transactions that are correlated (as part of a unitary storage operation) using consistent tag values. For example, in some embodiments, some storage operations are effectuated using address transactions that convey address information to target devices and to other devices (e.g., processors and caches that snoop address transactions). Address-response transactions then convey target and/or coherence responses from respective targets and snoopers). Finally, data transactions convey addressed data from a target or intervening device (e.g., a cache containing a modified version of a coherency granule or cache line) to or from the requester and/or a memory subsystem. While the set of implemented operations will, in general, be implementation-specific, examples of storage operations in typical embodiments include (without limitation): <ul><li id="ul0001-0001" num="0000"><ul><li id="ul0002-0001" num="0027">load operations initiated by processors (e.g., based on execution on a processor <b>101</b> of a load instruction that misses in its associated local cache <b>11</b>),</li><li id="ul0002-0002" num="0028">store operations initiated by processor(s) <b>101</b> or I/O devices <b>103</b> (via I/O bridge <b>110</b>), and</li><li id="ul0002-0003" num="0029">coherence-oriented operations such as data cache flush operations or translation lookaside buffer (TLB) synchronize operations. <br /> As described herein, such operations may be initiated in coherency interconnect <b>104</b> by a requesting device using an appropriate address transaction and completed using subsequent coherency response and data transactions, together with any transactions. </li></ul></li></ul>

p-0028As a general proposition, some devices may act as master-only devices that can initiate address and data transactions, but do not themselves contain addressable memory locations that can be accessed by other devices; some devices may act as target-only devices that contain addressable memory locations that are the targets of address and data transactions, but which do not themselves initiate such transactions; and some devices are combination devices that may act as both initiators and targets of address and data transactions. Often, processors and direct memory access (DMA) engines act as master-only devices, memory subsystems and I/O devices that have addressable memory but no on-board DMA controller act as target devices. In some cases, devices such as a processor that exposes backside memory to other masters or I/O devices that include both addressable storage and DMA facilities may act as combination devices, i.e., as both masters and targets.

p-0029In some embodiments, a substantial portion of a computational system such as illustrated in <figref idrefs="DRAWINGS">FIG. 1</figref> is implemented as a system on a chip (SoC) and embodied as a single integrated circuit chip. In such configurations, memory <b>102</b>, <b>12</b> and/or a subset of I/O devices <b>103</b> or interfaces may be implemented on- or off-chip, while the substantial entirety of illustrated blocks are packaged as an SoC. However, in other embodiments and more generally, portions of computational system <b>100</b> may be implemented in or as separate integrated circuits in accord with design, packaging or other requirements.

p-0030In some embodiments, computational system <b>100</b> is configured as a partitionable multiprocessor system in which storage operations involving particular addressable locations (including I/O device locations) may be confined to a particular partition (or partitions) to which they correspond. In such embodiments, isolation of partitions may be achieved using conventional memory management mechanisms (e.g., MMUs and TLBs, not specifically shown) and using device authorization mechanisms and address and operation type checking performed at an I/O Bridge <b>110</b> using facilities of an IOMMU). Although not essential to any particular embodiment, flexible, even dynamic, partitioning of underlying hardware may be facilitated using modern virtualization technologies (e.g., hypervisors) that execute on underlying resources of computational system <b>100</b> (e.g., processors <b>101</b>, memory <b>102</b>, <b>12</b> and I/O devices <b>103</b>) and expose fractional portions thereof to guest computations (e.g., operating system instances and applications) as virtual machines or partitions. Virtualization technologies are widely employed in modern computational systems and, particularly with regard to processor and memory virtualization, suitable designs and the operation thereof are well understood by persons of ordinary skill in the art. In some embodiments, a firmware-based hypervisor may be employed.

h-0005Device Interfaces and Signals

p-0031As a general matter, embodiments in accordance with the present invention are envisioned in which signals or information at a transaction layer (e.g., at a layer which corresponds to operations and the constituent transactions which implement such operations) and signals or information at a physical layer need not correspond in a one-to-one manner. Indeed, signals or information at a transaction layer may be represented as independent parallel channels while corresponding signals or information may, at the physical layer, be transmitted, encoded or conveyed using channels or paths that need not precisely correspond to the transaction layer. At least in part for this reason, much of the description that follows refers to physical layer signal paths (such as those that conveyed transactions between devices (e.g., processors <b>101</b>, on-chip cache memory <b>105</b> and I/O bridge <b>110</b>) and coherency interconnect <b>104</b> as links and transaction-oriented subsets of such physical layer signal paths as sub-links.

p-0032Of course, collections of multi-bit fields defined for conveyance of transaction information grouped as a sub-link and, indeed collections of information associated with one or more of the constituent sub-links of a link may be jointly encoded, multiplexed or otherwise commingled such as in a serial bus. Nonetheless, for simplicity and clarity (though without loss of generality), the description herein assumes that transactions are signaled in a “native” manner such that physical layer signals correspond one-to-one with signals at the transaction layer. Thus, in the description that follows sub-links correspond, in a one-to-one manner, with groups of multi-bit fields defined for conveyance of particular type of transaction information. Based on the description herein, persons of ordinary skill in the art will appreciate suitable physical layer modifications and extensions for embodiments in which transactions and at least some interfaces are not signaled in a “native” manner. In some embodiments, multiple companion instances of a particular sub-link may be provided.

h-0006Operations and Transactions

p-0033Some embodiments in accordance with the present invention allow devices interconnected using coherency interconnect <b>104</b> (and links thereto and therefrom) to perform several types of storage operations such as reading or writing of storage locations, synchronization, etc. Each operation is effectuated using multiple transactions, or self-contained, atomic units of information, transferred between two or more entities. In general, an operation causes one or more transactions to occur in the system.

p-0034In the illustrated embodiments, there are three types of transactions: Address, Address Response, Data. This classification or labeling of transactions carries through to naming conventions adhered to in describing the type of bus or sub-link utilized in transmitting the transaction. Each type of transaction will be understood relative to the corresponding type of bus or sub-link, directed either in or out of the device.

p-0035As a general proposition, an operation is submitted by a device into the system as an address transaction. It subsequently incurs multiple address response transactions. Depending on the operation and the current state of the caches in the system, the operation may also incur one or more data transactions. Because an operation starts its life in the system as an address transaction, the operation is often conveniently referred to using the name or type of the initiating address transaction.

p-0036An operation that does not incur a data transaction, is informally referred to as an “address-only” operation; one that does is referred to as “address-data operation.” Note that since occurrence of data transactions is a function of the state of the system, an operation might be address-only at one time and address-data at another.

p-0037The three types of transaction found in CoreNet are described now. <ul><li id="ul0003-0001" num="0000"><ul><li id="ul0004-0001" num="0040">Address transactions are issued for sending the command portion of an operation, e.g., “read” for reading data, “sync” for achieving synchronization, etc.</li><li id="ul0004-0002" num="0041">Data transactions are issued either in response to address transactions, as in the case of a read transaction (for returning data for the read operation) or as transactions accompanying the address transactions, as in the case of a write operation (for delivering data for a memory write operation).</li><li id="ul0004-0003" num="0042">Address Response transactions are issued as responses to address transactions, e.g., for indicating if there was an error in receiving a transaction or reporting a coherency response such as the global status of a coherency granule or cache line.</li></ul></li></ul>

p-0038Some devices like processors can produce all types of transactions, but not all devices are so capable. Broadly speaking, devices that are able to issue address transactions are called “master devices;” those which cannot are called “target devices.” Different transactions are issued using the appropriate sub-links. Of course, not all signals or sub-links are required to be implemented by a given device. Neither is full width of a given signal mandatory throughout the system. Depending on the types of transactions supported by a device, it connects to the system only via the signals necessary to receive or issue them. Thus, for example, a device that does not issue an address transaction need not have signals used to control and transmit the out-bound flow of address transactions.

p-0039Transactions that correspond to the same operation are correlated with each other. For example, in some embodiments, each such transaction bears a corresponding tag suitable for propagation through the links, interconnect and devices of a computational system and for use by coherency interconnect <b>104</b> in correlating related transactions.

h-0007Links and Sub-Links

p-0040<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram that illustrates, in further detail and in accordance with some embodiments of the present invention, sub-links and related interfaces between coherency interconnect <b>104</b> (on the one hand) and instances of a processor <b>101</b>, cache <b>105</b> and I/O bridge <b>110</b> (on the other). In the illustrated configuration, respective bus-type sub-links or signal groups are provided for conveying address transactions (e.g., via instances of sub-links ABusOut and ABusIn), for conveying address response transactions from target devices (e.g., via instances of sub-links ATRBusOut and ATRBusIn), for conveying coherence-type address response transactions from snoopers (e.g., via instances of sub-links ACRBusOut and ACRBusIn), and for conveying data transactions (e.g., via instances of sub-links DBusOut and DBusIn). As shown, respective collections of bus-type sub-links (including device appropriate subsets of the sub-links) define respective point-to-point links <b>201</b>, <b>205</b> and <b>210</b> with coherency interconnect <b>104</b>. For simplicity, bus-type interfaces (e.g., device interfaces <b>291</b> and interconnect interfaces <b>294</b>) are shown collectively for respective collections of sub-links, but may be understood as individual and independent bus-type signaling interfaces for each of the respective sub-links. Note that in <figref idrefs="DRAWINGS">FIG. 2</figref> (and those that follow), a device-centric view-point, with ordering points outside the device, is taken in characterizing the In or Out directionality of sub-links.

p-0041In the illustrated embodiment, coherency interconnect <b>104</b> includes distinct address path <b>292</b> and data path <b>293</b> portions that convey respective signals or information amongst the interconnected devices. For example, in the course of some storage operations and subject to request/grant protocols described below, signals associated with constituent address transaction are conveyed from processor <b>101</b> to coherency interconnect <b>104</b> via sub-link ABusOut and respective interfaces. Address path <b>292</b> conveys the signals or information for an address transaction to interfaces <b>294</b> for appropriate devices (typically including the initiating device, processor <b>101</b>, addressed target device and any snoop devices) via a pipelined bus, point-to-point or other suitable interconnect path. Respective ABusIn sub-links and device interfaces <b>291</b> convey the signals or information to respective devices.

p-0042For purposes of illustration, <figref idrefs="DRAWINGS">FIG. 2</figref> depicts an example field and signal decomposition <b>295</b> of sub-link ABusOut by which an address transaction is conveyed from processor <b>101</b> to coherency interconnect <b>104</b>, including principally an illustrative 6-bit field Type and an illustrative 64-bit field AOut by which the address transaction type, e.g., read, read with intent to modify (RWITM), flush, write for cast out (WCO), etc., and a target memory address are coded. Size field Sz codes the data transfer size, which, if greater than the width provided by the companion sub-link (i.e., sub-link DBusOut or DBusIn, depending on directionality), may require multiple successor data transaction beats. Tag field Tag codes a unique identifier that is conveyed with the address transaction and is propagated by devices and included in corresponding transactions (e.g., in subsequent address response, data and other address transactions) that are constituents of a particular operation. Contents of field Tag are used by coherency interconnect <b>104</b> to correlate related transactions. In the illustrated example, individual indications of class of transaction field CoT[0:N] code, in a one-hot format, the class of the particular transaction conveyed on sub-link ABusOut. Note the classes of transactions, together with related request (AOutR[0:N]) and grant (AOutG[0:N]) flow control signals <b>281</b> are described in greater detail below. Valid field V, when asserted, indicates that sub-link signals are valid. Other address transaction related sub-links, e.g., sub-links <b>296</b>, <b>297</b> and <b>298</b> (ABusIn) and sub-link <b>299</b> (ABusOut), are of similar format and include analogous fields.

p-0043Likewise for data transactions, signals associated with a data transaction are conveyed from a respective data source (e.g., from a target device such as the memory subsystem illustrated as memory controller <b>106</b> and its associated cache <b>105</b>) to coherency interconnect <b>104</b> via corresponding sub-link DBusOut and the associated interfaces. Coherency interconnect <b>104</b> receives and buffers the data transactions and conveys same, via data path <b>293</b> to interfaces for an appropriate device or devices. In some embodiments, data path <b>293</b> implements a crossbar interconnect. Signals associated with a data transaction are delivered to the appropriate device or devices (e.g., to processor <b>101</b>) via the corresponding DBusIn sub-links and interfaces. Analogous address response signals are conveyed via coherency interconnect <b>104</b> and analogous directional sub-links ACRBusOut and ACRBusIn (for coherence responses from snoopers) and ATRBusOut and ATRBusIn (for target device responses).

h-0008Class of Transaction Framework

p-0044To maintain coherency or due to a resource dependency, a transaction may evoke a successor transaction from another device that must be completed before the original transaction can itself complete. In such a case, the original transaction is a predecessor transaction and is said to be dependent on the successor transaction. Evocation of secondary transactions can be transitive and can lead to a chain of transaction dependencies. In general, the length of any such chain depends on the operation performed and the constituent transactions thereof, but is also a function on the extent and structure of the particular system and the specific underlying protocol employed in it to achieve coherence, consistency, ordering, and other semantics of the storage related operations performed in the system.

p-0045<figref idrefs="DRAWINGS">FIG. 3</figref> is a dependency graph that depicts dependencies amongst constituent transactions of various illustrative operations in a coherency interconnect together with an illustrative assignment of class of transaction labels (CoT=0 . . . 4) to constituent transactions in coherence interconnect configurations such as illustrated in <figref idrefs="DRAWINGS">FIGS. 1 and 2</figref>. In particular, <figref idrefs="DRAWINGS">FIG. 3</figref> depicts, in accordance with some embodiments of the present invention, dependencies amongst respective constituent transactions of a load operation <b>301</b>, of a store operation <b>302</b>, of a data cache flush operation <b>303</b> and of a TLB synchronize operation <b>304</b>. Other operations may be, and typically are, supported in a given implementation. Likewise, different constituent transactions may be supported in some implementations. Nonetheless, the sets illustrated in <figref idrefs="DRAWINGS">FIG. 3</figref> provide a useful descriptive context and, based on the description herein, persons of ordinary skill in the art will appreciate suitable CoT frameworks for larger and/or different set of operation and/or constituent transactions.

p-0046Although any of a variety of coding schemes may be employed, in illustrative device and coherency interconnect implementations described herein, transaction information conveyed via sub-links tends to distinguish between transactions based on type and dependencies on possible successor transactions by encoding a class of transaction label CoT, where 0≦CoT≦MAX_CoT-1. In general, a sufficient number of distinct CoTs are provided to ensure that a given implementation can apply an ordered set of CoT labels to respective transactions along the longest dependency chain that is possible in a given implementation. For the set of operations and constituent transactions illustrated in <figref idrefs="DRAWINGS">FIG. 3</figref>, an ordered set of CoT labels {0, 1, 2, 3, 4} is sufficient. In other situations or embodiments, larger of small sets of CoT labels may be needed or sufficient.

h-0009Resource Independence between CoT Classes

p-0047In general, by assigning and applying CoT labels coded using any desirable or suitable scheme, embodiments of the present invention facilitate architectural mechanisms for assuring forward progress or deadlock-freedom properties in coherency interconnect <b>104</b> (recall <figref idrefs="DRAWINGS">FIGS. 1</figref>, <b>2</b>) and devices interconnected therewith. To accomplish this, implementations should ensure that a given transaction will not be blocked permanently from making progress because of resource conflicts with transactions having lower CoTs. Accordingly, implementations may maintain independence of transactions of different CoTs with respect to the resources they utilize. In general, this implies that a minimum of one resource is reserved for each of the CoTs.

p-0048Note that the above requirement does not imply a scheduling policy. An implementation may, for performance consideration, allow a specific CoT transaction to bypass a transaction with a different CoT, or allow a transaction to bypass another transaction with the same CoT, except when explicit ordering is called for.

h-0010Resource Independence within a CoT Class

p-0049An implementation should also guarantee that no circular resource dependencies can arise within a single class of transaction. That is, no two (or more) transactions of the same CoT should, for want of a resource (or resources), be dependent upon each other such that neither (or none) can complete. Depending on the structure of the system, in order to prevent circular resource dependencies between transactions of the same CoT and thus prevent deadlock, the system may be required to have certain minimum number—greater than 1—of resources reserved for a particular CoT. For example, in a computational system in which each of N devices may initiate remote snoop requests (for which a particular CoT=X is assigned) with respect to addressed locations that may be cached by its peers, it may be necessary for a coherency interconnect to reserve for any particular device, N-1 resources suitable for completion of a CoT=X transaction. In this way, flow controls may assure that any given operation that is allowed to initiate and includes in its dependency chain snoop requests directed to its peers may complete and not block progress of its peers. Alternatively, in some cases, an implementation may simply increase the number of CoT classes to accommodate in a piecewise manner the minimum number of resources that must be reserved for a given CoT.

p-0050By assigning CoT labels in a manner that captures dependencies amongst transactions and assures sufficient resources for completion of all successor transactions upon which a give transaction depends, it is possible to provide flow controls that preclude cyclic chains of dependencies amongst transactions due to resource constraints and which therefore avoid system deadlock without retries. To provide architectural support for the foregoing, some embodiments of the present invention require that:

p-0051CoT(Predecessor transaction)&lt;CoT(Successor transaction).

p-0052Where the transactions assigned the highest class, i.e., CoT=MAX_CoT-1, must not evoke any other transactions. In general, transactions that do not evoke successor transactions, and which therefore have no further dependent transactions, are termed terminal transactions. Remaining transactions are termed non-terminal transactions. Based on the foregoing, it will be understood that transactions assigned the highest class must be terminal transactions. However, the terminal transaction of any given operation need not be of the highest class.

p-0053While the ordering of CoTs illustrated with respect to the described embodiments herein is from a lowest ordinal to a highest, such ordering is simply a matter of convention and other embodiments may adopt other conventions. In general, the number of CoTs needed in a computational system is dictated by the longest transaction dependency chain that might occur. However, the actual number of CoTs employed or exposed in a system may be affected by implementation-dependent factors. For example, it is possible for a given implementation of coherency interconnect <b>104</b> and interconnected devices to not expose some transaction dependencies architecturally via the CoT assignments, but rather to provide for them in appropriate resource allocation policies. In some embodiments, dependency chains (or resource allocation policies) also account for dependencies created by I/O ordering rules, if any.

p-0054In general, devices are nominally expected to manage their own internal resources as necessary to guarantee forward progress for any transactions it originates and the secondary transactions that might arise as side effects of the original transactions. An example of this is a write with cast out (WCO) transaction that might arise within a processor as a result of a read transaction that replaces a modified coherency granule or cache line. If a device is unable to manage its own internal resources, embodiments of the present invention may seek to accommodate through increase the number of CoT labels supported and higher system complexity.

p-0055Finally, a device is expected to be aware of and use the number of different CoTs it needs for its transactions but not necessarily the allocation of those CoTs within the CoT mapping employed by the overall system. Thus, a device may label transactions that it initiates with CoTs according to a locally consistent scheme (e.g., starting at 0 and defining only locally-valid labels) as long as a consistent mapping from the device's CoT labeling scheme to system CoTs may be performed in the connectivity between the device and the coherency interconnect.

p-0056Turning again to <figref idrefs="DRAWINGS">FIG. 3</figref>, dependencies amongst possible chains of successive constituent transactions are depicted together with assigned CoT labels for various illustrative operations in a coherency interconnect (such as coherency interconnect <b>104</b>). In particular, relative to the possible constituent transactions of store operation <b>302</b>, it will be understood that an initiating address-type transaction (here a read with intent to modify, RWITM, transaction <b>321</b> may be used to secure modify access to a coherency granule corresponding to an addressed memory location, whereupon a successor address-type transaction (here a write with cast out, WCO, transaction <b>322</b>) actually initiates the write to memory which is completed with data committed to memory using data-type transaction <b>323</b>. Finally, a second data-type transaction <b>324</b> conveys data from the targeted location to devices that cache contents of the corresponding coherency granule. To properly order the successive transactions along the dependency chain for store operation <b>302</b> while accommodating a CoT=0 label for TLBSYNC transaction <b>341</b>, RWITM transaction <b>321</b> is labeled as a CoT=1 and successive WCO (<b>322</b>) and data transactions (<b>323</b>, <b>324</b>) are labeled (in accord with the illustrated precedence order) as CoT=2, CoT=3 and CoT=4, respectively.

p-0057With respect to possible constituent transactions of load operation <b>301</b>, it will be understood that, following an initiating address-type transaction (here a read transaction <b>311</b> that conveys a memory address from a processor device to a target device and to one or more snoop devices), two possibilities present. In some situations, a coherency response (illustrated by a modified-intervention, M-INT, address-response-type transaction <b>312</b>) is supplied from a snoop device signifying that the corresponding cache currently has a copy of the coherency granule that is modified with respect to memory. In such case, an intervention data-type transaction <b>313</b> conveys the modified data from the intervening cache to the processor that initiated read transaction <b>311</b>. In some situations, a null response (illustrated by NULL, address-response-type transaction <b>314</b>) signifies that the read may be satisfied from the target memory subsystem and primary data-type transaction <b>315</b> conveys the addressed data from the target device to the processor that initiated read transaction <b>311</b>.

p-0058Successive transactions along the illustrated dependency chain for load operation <b>301</b> are labeled in a manner consistent with the labeling applied for possible dependency chains associated with store operation <b>302</b> and accommodating a CoT=0 label for TLBSYNC transaction <b>341</b>. In particular, initiating address-type READ transaction <b>311</b> is labeled as a CoT=1 and primary data-type transaction <b>315</b> and intervention data-type transaction <b>313</b> are each labeled as CoT=4, in accord with the illustrated precedence order and consistent with CoT labeling of similarly situated data transaction <b>324</b> of store operation <b>302</b>.

p-0059Constituent transactions of data cache flush operation <b>303</b> include an initiating address-type transaction (here a flush transaction <b>331</b>) that conveys a memory address from a processor device to a target device that caches the coherency granule and to one or more snoop devices, whereupon a successor address-type transaction (here a write with cast out, WCO, transaction <b>332</b>) actually initiates the write of cached date to memory using data-type transaction <b>333</b>. A NULL address-response-type transaction <b>334</b> signifies completion relative to the initiating flush transaction <b>331</b>.

p-0060As before, successive transactions along the illustrated dependency chain for data cache flush operation <b>303</b> are labeled in a manner consistent with the labeling applied for possible dependency chains associated with store operation <b>302</b> and in a way that accommodates a CoT=0 label for TLBSYNC transaction <b>341</b>. In particular, initiating address-type FLUSH transaction <b>331</b> is labeled as a CoT=1, while successive WCO transaction <b>332</b> and its corresponding primary data transaction <b>333</b> are labeled (in accord with the illustrated precedence order) as CoT=2 and CoT=3, respectively.

p-0061Finally, TLB synchronize operation (TLBSYNC) address transaction <b>304</b> is labeled as CoT=0 because completion of a TLBSYNC requires completion of all in-flight active transactions in the computational system that may have utilized previous page table translations. Since a given instance of TLBSYNC transaction <b>304</b> may depend upon transactions of any of the other operations supported which may be in-flight, a label of CoT=0 properly codes the possible dependency on transactions labeled as CoT=1, CoT=2, CoT=3 or CoT=4. Building on the acyclic precedence orders of transactions and a framework of CoT labels such as illustrated in <figref idrefs="DRAWINGS">FIG. 3</figref>, persons of ordinary skill in the art will appreciate flow controls implemented in some embodiments of coherency interconnect <b>104</b>.

h-0011Transaction Flow Control

p-0062Referring now to <figref idrefs="DRAWINGS">FIG. 4</figref>, transaction flow controls are illustrated for an address-type transaction initiated by processor <b>101</b> via sub-link ABusOut of link <b>201</b> with coherency interconnect <b>104</b>. As before, an example field and signal decomposition <b>295</b> is illustrated. Field definitions and variations remain consistent with those described with reference to <figref idrefs="DRAWINGS">FIG. 2</figref>, while request and grant signals and logic for flow control on sub-link ABusOut are illustrated in further detail.

p-0063As a general proposition, linked entities such as processor <b>101</b> and coherency interconnect <b>104</b> may be required (in some embodiments) to seek permission of the other to send transactions over unidirectional address and data buses (e.g., over illustrated sub-links ABusOut, ABusIn, DBusOut and DBusIn using a flow control mechanism such as may be provided using request and grant signals. Entities each include flow control units that process these requests and issue grants based on the local resource status. After receiving the grant signal, the requester may drive the corresponding bus signals and effect the sending of a transaction. Although flow controls may be applied for any transaction or sub-link and for any of a variety of purposes including throttling based on local load or resource states, the primary focus of the present description is on use of a CoT-denominated request-grant mechanism and protocol relative (primarily) to address-type transactions that initiate an operation (and the possible sequences of successive transactions that are constituents of such an operation).

p-0064Accordingly, for purposes of clarity and specificity, the description focuses on CoT-denominated requests and grants used relative to initiating address-type transactions that a device (e.g., processor <b>101</b>) seeks to convey to coherency interconnect <b>104</b> via a corresponding sub-link ABusOut. Other requests and grants (including, in some cases, CoT-denominated requests and grants) may be used for other sub-links and for other devices. However, relative to a framework of CoT labels selected and applied as described above and with reference to <figref idrefs="DRAWINGS">FIG. 3</figref>, persons of ordinary skill in the art will appreciate the attractiveness of making control flow decisions, i.e., providing CoT-denominated grants in response to CoT-denominated requests, based on the CoT for an initiating address-type transaction. In this way, consistent with assumptions encoded in the CoT framework, coherency interconnect <b>104</b> may (1) consider a request based (implicitly) on compatibility of the requested transaction and its possible successors availability of interconnect resources required therefor and (2) reserve those required resources in conjunction with a corresponding grant.

p-0065Thus, <figref idrefs="DRAWINGS">FIG. 4</figref> illustrates a device, here processor <b>101</b>, requesting (<b>441</b>) to drive sub-link ABusOut with a transaction of CoT[i], where 0≦i≦MAX_CoT-1. In general, a device may concurrently assert CoT-denominated requests for multiple values i and coherency interconnect <b>104</b> may assert (concurrently or otherwise) corresponding grants for one or more of the multiple values i; however, for simplicity of description, a single request is considered. Persons of ordinary skill in the art will appreciate extrapolations to multiple concurrent requests. In any case, request-grant logic <b>401</b> of processor <b>101</b> awaits (<b>442</b>) a CoT-denominated grant from its link partner, coherency interconnect <b>104</b>. Some time after the signal ABOutR[i] is asserted and received (<b>451</b>), an arbiter of request-grant logic <b>402</b> checks (<b>452</b>) to ensure that given CoT denominated transactions already in-flight and resources reserved therefor (including for possible successors), sufficient resources remain unallocated to allow a transaction of the class requested by signal ABOutR[i] together with its possible successors to complete, and if so, asserts (<b>453</b>) the corresponding signal ABOutG[i]. Sometime subsequent to the assertion of ABOutG[i], the address transaction is conveyed from processor <b>101</b> to coherency interconnect <b>104</b> over sub-link ABusOut.

p-0066Although any of a variety of mechanisms may be employed at coherency interconnect <b>104</b> to facilitate arbitration by request-grant logic <b>402</b>, one straightforward implementation preferentially grants higher CoT requests prior to considering lower CoT requests and assumes in its decision logic, for a request signal ABOutR[i], that coherency interconnect <b>104</b> must have sufficient unreserved resources to satisfy a transaction at CoT[i] and at every CoT. In general, reservations of resources may be explicitly encoded in transaction table <b>403</b> (or elsewhere) or may be implicit based on resources associated (or associable) with a set of in-flight transactions specifically represented in transaction table <b>403</b> (or elsewhere) and potential successors of such specifically represented transactions and resources associated (or associable) therewith. If sufficient resources are available, decision logic issues the corresponding grant signal ABOutG[i] and update transaction table <b>403</b> (or any other suitable store) to reflect the explicit or implicit reservation of resources.

p-0067In the illustration of <figref idrefs="DRAWINGS">FIG. 4</figref>, CoT-denominated requests are represented (<b>461</b>) in a positionally-encoded format AOutR[0:N] where each asserted position encodes a request to initiate an address transaction of the corresponding CoT on sub-link ABusOut. Likewise, CoT-denominated grants are represented (<b>462</b>) in a positionally-encoded format AOutG[0:N] where each asserted position encodes grants for address transactions of the corresponding CoT on sub-link ABusOut. In some embodiments, CoT-denominated grants are unconditional and allow a device, e.g., processor <b>101</b>, to initiate an address transaction via sub-link ABusOut at a future time of its choosing. In general, no transmission window need be required and if a device, e.g., processor <b>101</b>, has received multiple CoT-denominated grants (potentially for transactions of differing CoTs), it may initiate corresponding address transactions in orders and at future times of its selection. Address transactions, when eventually presented on sub-link ABusOut, based on a then outstanding CoT-denominated grant, encode the corresponding CoT-label.

h-0012Ordering of Transactions

p-0068Once a device has successfully navigated the above-described request-grant protocol and presented its address transaction on a corresponding sub-link ABusOut, the transactions are subject to ordering at coherency interconnect <b>104</b>. <figref idrefs="DRAWINGS">FIG. 5</figref> illustrates ordering points <b>501</b>, <b>502</b> employed in and address path <b>292</b> of some implementations of coherency interconnect <b>104</b>. In particular, coherency interconnect <b>104</b> receives and buffers incoming address transactions, including instances of address transactions (such as RWITM, READ, FLUSH and TLBSYNC transactions, recall <figref idrefs="DRAWINGS">FIG. 3</figref>) that initiate operations in coherency interconnect <b>104</b>. Address path <b>292</b> includes two ordering points <b>501</b>, <b>502</b> that, subject to some appropriate discriminator, have purview over respective subsets of received address transactions. For example, in some embodiments, address transactions targeting distinct portions of an address space may be ordered separately, e.g., using ordering point <b>501</b> to order transactions that target a first portion of the coherency domain and using ordering point <b>502</b> to order transactions that target a second portion). In some embodiments, only a single ordering point may be provided.

p-0069In general, address transactions received from a particular device (e.g., from processor <b>101</b>, cache <b>105</b>, or I/O bridge <b>110</b>), are supplied to a target of the address transaction and to any appropriate snoop devices via corresponding sub-links ABusIn. For simplicity of illustration, other sub-links are omitted in <figref idrefs="DRAWINGS">FIG. 5</figref>. Ordering imposed by ordering point <b>501</b> and/or ordering point <b>502</b> may be in accord with any suitable or desirable transaction ordering framework. For example, ordering may be in accord with ordering semantics defined for the Power Architecture (i.e., nominally weakly ordered, but with strong ordering enforced on demand via explicit synchronization operations) or in accord with ordering semantics specified by a peripheral component interconnect (PCI) Local Bus Specification or in accord with AXI semantics. In some embodiments, an operant ordering framework may be specified by the initiating device (e.g., processors <b>101</b>).

h-0013Data Transactions

p-0070As previously described, class of transaction CoT labels may optionally be applied to data transactions in some embodiments of the present invention. <figref idrefs="DRAWINGS">FIG. 6</figref> illustrates, relative to an exemplary data transaction coding format <b>695</b>, sub-links and related interfaces between coherency interconnect <b>104</b> (on the one hand) and instances of a processor <b>101</b>, cache <b>105</b> and I/O bridge <b>110</b> (on the other). As before, respective bus-type sub-links or signal groups are provided for conveying address transactions (e.g., via instances of sub-links ABusOut and ABusIn), for conveying address response transactions from target devices (e.g., via instances of sub-links ATRBusOut and ATRBusIn), for conveying coherence-type address response transactions from snoopers (e.g., via instances of sub-links ACRBusOut and ACRBusIn), and for conveying data transactions (e.g., via instances of sub-links DBusOut and DBusIn). Also as before, respective collections of bus-type sub-links (including device appropriate subsets of the sub-links) define respective point-to-point links <b>201</b>, <b>205</b> and <b>210</b> with coherency interconnect <b>104</b>. For simplicity, bus-type interfaces (e.g., device interfaces <b>291</b> and interconnect interfaces <b>294</b>) are shown collectively for respective collections of sub-links, but may be understood as individual and independent bus-type signaling interfaces for each of the respective sub-links.

p-0071In the course of some storage operations and subject to request/grant protocols that may, in some embodiments, be applied to data transactions, signals associated with a particular data transaction are conveyed from processor <b>101</b> to coherency interconnect <b>104</b> via sub-link DBusOut and respective interfaces. Data path <b>293</b> conveys the signals or information for an address transaction to interfaces <b>294</b> for appropriate devices (typically the addressed target device) via a crossbar interconnect, pipelined bus or other suitable interconnect path. Respective DBusIn sub-links and device interfaces <b>291</b> convey the signals or information to the target device (or devices).

p-0072As with previously described address transaction codings, <figref idrefs="DRAWINGS">FIG. 6</figref> depicts an example field and signal decomposition <b>695</b> of sub-link DBusOut by which a data transaction is conveyed from processor <b>101</b> to coherency interconnect <b>104</b>, including principally an illustrative field Type and DOut by which the data transaction type, e.g., primary data, intervention data, etc., and at least a portion of a data payload are coded. Field Beat codes a beat index for data transfers that, based on the data transfer size, may require multiple data transactions. In general, a beat index need not be provided unless the width provided by the DBusOut sub-link (or analogously by sub-link DBusIn) is insufficient to convey the data payload in a single transaction beat. In some embodiments, a size field may be employed. Tag field Tag codes a unique identifier that is conveyed with the data transaction and is propagated by devices and included in corresponding transactions (e.g., in subsequent address response, data and other address transactions) that are constituents of a particular operation. Contents of field Tag are consistent across address, address response and data transactions that are constituents of the same operation and are used by coherency interconnect <b>104</b> to correlate related transactions.

p-0073An optional class of transaction label CoT[0:N] codes, in a one-hot format, the class of the particular transaction conveyed on sub-link DBusOut. In embodiments that implement CoT labels for data transaction, related request (DOutR[0:N]) and grant (DOutG[0:N]) flow control signals <b>681</b> may be provided and employed in a manner analogous to request-grant signals and in accord with protocols analogous to those described above (with reference to <figref idrefs="DRAWINGS">FIG. 4</figref> and address transactions). Valid field V, when asserted, indicates that sub-link signals are valid. Other data transaction related sub-links, e.g., sub-links <b>696</b>, <b>697</b> and <b>698</b> (DBusIn) and sub-link <b>691</b> and <b>692</b> (DBusOut), are of similar format and include analogous fields.

h-0014Other Embodiments

p-0074Although the invention is described herein with reference to specific embodiments, various modifications and changes can be made without departing from the scope of the present invention as set forth in the claims below. For example, while techniques have been described in the context of illustrative devices, interfaces, topologies and signals, the described techniques have broad applicability designs in which other or additional devices, interfaces, topologies and signals are supported. Class of transaction (CoT) techniques and labels have been described as an ordered set of values that may span transaction types (e.g., address and data transactions alike). However, more generally, CoTs can be represented as an n-tuple and the CoT space could be multi-dimensional, each element in the tuple corresponding to the distinct type of resource needed by the transactions. Furthermore, although embodiments detailed herein map the transaction (of multiple types) to a single linear order of classes, multiple subsets (e.g., one subset representing address transaction related resources and the another subset representing data transaction related resources) may be implemented or supported in other embodiments.

p-0075Embodiments of the present invention may be implemented using any of a variety of different information processing systems. Of course, architectural descriptions herein have been simplified for purposes of discussion and those skilled in the art will recognize that illustrated boundaries between logic blocks or components are merely illustrative and that alternative embodiments may merge logic blocks or circuit elements and/or impose an alternate decomposition of functionality upon various logic blocks or circuit elements.

p-0076Articles, systems and apparati that implement the present invention are, for the most part, composed of electronic components, circuits and/or code (e.g., software, firmware and/or microcode) known to those skilled in the art and functionally described herein. Accordingly, component, circuit and code details are explained at a level of detail necessary for clarity, for concreteness and to facilitate an understanding and appreciation of the underlying concepts of the present invention. In some cases, a generalized description of features, structures, components or implementation techniques known in the art is used so as to avoid obfuscation or distraction from the teachings of the present invention.

p-0077Finally, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and consistent with the description herein, a broad range of variations, modifications and extensions are envisioned. Any benefits, advantages, or solutions to problems that are described herein with regard to specific embodiments are not intended to be construed as a critical, required, or essential feature or element of any or all the claims.