Patent ID: 12197918

Reference symbols in the various drawings that have the same number indicate like elements.

DETAILED DESCRIPTION

In the following descriptions, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding. One or more embodiments may be practiced without these specific details. Features described in one embodiment may be combined with features described in a different embodiment. In some examples, well-known structures and devices are described with reference to a block diagram form in order to avoid unnecessarily obscuring the present invention.

Details of particular embodiments are provided with respect to the various drawings and the descriptions below. Other enhancements, features, details, and/or advantages of the particular embodiments may be ascertainable by those of skill in the art upon reading the present descriptions and viewing the drawings.

Also, the particular embodiments described herein may be implemented in any computing system environment known in the art, which may include one or more processors and a computer-readable medium configured to store logic, the logic being implemented with and/or executable by the one or more processors to cause the one or more processors to perform operations specified by the logic.

The descriptions presented herein relay sufficient information to enable a person having ordinary skill in the art to make and use the present invention and are provided in the context and requirements of particular embodiments of the present invention.

It is also noted that various modifications to the disclosed embodiments will be readily apparent to a person having ordinary skill in the art and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown and described herein, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

Also, unless otherwise specifically defined herein, all terms are to be given their broadest possible interpretation including meanings implied from the specification as well as meanings understood by a person having ordinary skill in the art and/or as defined in dictionaries, treatises, etc.

Moreover, the term “about” when used herein to modify a value indicates a range that includes the value and less and greater than the value within a reasonable range. In the absence of any other indication, this reasonable range is plus and minus 10% of the value. For example, “about 10 milliseconds” indicates 10 ms±1 ms, such that the range includes all values in a range including 9 ms up to and including 11 ms. In addition, the term “comprise” indicates an inclusive list of those elements specifically described without exclusion of any other elements. For example, “a list comprises red and green” indicates that the list includes, but is not limited to, red and green. Therefore, the list may also include other colors not specifically described.1. GENERAL OVERVIEW2. SYSTEM ARCHITECTURE2.1 HARDWARE PIPELINE2.2 COMMAND BUNDLE2.3 SYSTEM OVERVIEW3. EXAMPLE EMBODIMENTS3.1 HARDWARE ROUTING MESH3.2 METHOD FOR PROCESSING A COMMAND3.3 METHOD FOR TRAVERSING A COMMAND BUNDLE4. MISCELLANEOUS; EXTENSIONS5. HARDWARE OVERVIEW

1. GENERAL OVERVIEW

One or more embodiments present a hardware routing mesh that includes sets of routing nodes that form one or more hardware pipelines. Many hardware pipelines may be included in the hardware routing mesh. Commands, grouped together in a command bundle, are streamed through a hardware pipeline via a control path. The command bundle is modified by the routing nodes based on execution of commands to achieve a desired outcome.

Each routing node within a hardware pipeline is associated with one or more hardware modules for processing commands. A routing node forwards commands to another routing node in the hardware routing mesh when (a) a command is not of a command type relevant to associated hardware module(s), or (b) all data needed to execute the command is not available when the command is received.

Moreover, a routing node transmits commands to at least one hardware module associated with the routing node for execution when (a) a command is of the command type relevant to associated hardware module(s), and (b) all data needed to execute the command is available when the command is received. Thereafter, the routing node modifies the command bundle based on execution of the command.

A routing node may also traverse a received command bundle to determine whether any commands of a particular command type relevant to associated hardware module(s) are included in the command bundle. When no commands of the particular command type are in the command bundle, the routing node transmits the command bundle, without modification, to a next routing node in the hardware pipeline.

This Specification may include, and the claims may recite, some embodiments beyond those that are described in this General Overview section.

2. SYSTEM ARCHITECTURE

A plurality of software applications may be executing on a computer system at any given time. Each software application provides a plurality of compute functions for execution by a processor of the computer system. For simplicity, it is assumed that a software application's compute functions may be divided into three different classes based on the computer system's architecture and ability to implement the compute functions: CPU-based architecture functions (for CPU implementation), GPU-based architecture functions (for GPU implementation), and hard program-based architecture functions (for ASIC and/or FPGA implementation).

CPUs and GPUs are built using well-defined architectures that are optimized for the class of compute functions they are most commonly expected to execute. This provides a common programming paradigm for software developers to build applications for CPUs and GPUs. However, a well-defined architecture does not exist for applications using FPGA-based platforms and/or ASIC-based platforms.

The methodology for how each ASIC-based platform and FPGA-based platform handle specific architectural attributes is unique to each application (e.g., custom for the application it is designed for). For example, each of these platform characteristics may be designed differently for any given ASIC-based platform and FPGA-based platform:1) Connections to external interfaces, e.g., interfaces to memory, peripheral component interconnect express (PCIe), media access control (MAC), etc.2) Transport and routing between compute functions3) Definition of instructions and data to execute compute functions4) Data coherency checks5) Data integrity checks6) Performance optimizations7) Debugging infrastructure

With an ASIC, the underlying design of compute functions, along with the definition and placement of the compute functions is predetermined and fixed. Therefore, these aspects of a typical ASIC cannot be reprogrammed or changed after manufacturing the ASIC. On the other hand, an FPGA may be reprogrammed after manufacture. However, every time a change is enacted to an existing compute function, and every time a new compute function is added, the underlying FPGA design is changed to accommodate these modified or added compute functions. This means that changes to typical ASIC-based platforms and FPGA-based platforms are expensive, e.g., they take time, have great complexity, and require tedious effort. Ultimately, these changes may lead to variability in performance and stability of the platform.

Therefore, for typical ASIC-based platforms and FPGA-based platforms, there is no common architecture or design system that software developers are able to utilize to build applications (unlike CPUs and GPUs).

An FPGA is a platform that is capable of being reprogrammed to create and combine custom accelerated compute functions that may be modified over and over again. In that sense, it is unlike a CPU, GPU, or ASIC whose architecture is designed and fixed by the vendor. FPGA compute functions may be developed independently by different independent developers, as opposed to a few large companies in the case of CPUs and GPUs, and put together in flexible ways to provide offloaded processing capacity for a range of applications.

However, for typical FPGA implementations, this is not possible. It may be difficult to arbitrarily combine compute modules developed by different developers within the same organization and installations, and nearly impossible across different organizations. This difficulty stems from the compute modules for these different FPGAs not being designed with a common interface or a common way of passing control and data between FPGAs and other processors.

2.1. Hardware Pipeline

FIG.1illustrates an example hardware pipeline100for processing commands in accordance with one or more embodiments. Hardware pipeline100presents a universal processor architecture that may be instantiated on an FPGA and/or ASIC-based platform, and may be optimized for the compute functions that are most commonly offloaded to the particular platform. As illustrated inFIG.1, hardware pipeline100includes multiple routing nodes102(e.g., routing node102a, routing node102b, routing node102c, . . . , routing node102n). Each routing node102is associated with a respective hardware module104(e.g., hardware module104a, hardware module104b, hardware module104c, . . . , hardware module104n) and is connected to its respective hardware module104for transmission of data/information between the routing node102and hardware module104. For example, routing node102ais communicatively coupled with hardware module104a, routing node102bis communicatively coupled with hardware module104b, etc.

A routing node102is a hardware device configured to receive a command bundle106via a control path112. The control path112is connected to each of the routing nodes102. Moreover, although the routing nodes102are shown being connected to the control path112and serially to one another, the routing nodes102may be selectively interconnected to one another in a hardware routing mesh capable of being modified dynamically to rearrange the order of the routing nodes102in the hardware pipeline100. By rearranging the order of the routing nodes102, it is possible to change how commands within the command bundle106are processed by the hardware pipeline100, as described in more detail with reference toFIG.2.

Referring again toFIG.1, a command bundle106is streamed through the various routing nodes102in the order in which they are connected to the control path112. The command bundle106is modified based on execution of commands from the command bundle106as the command bundle106is streamed through the various routing nodes102. For example, if routing node102bperforms a specific command from the command bundle106, this specific command may be removed from the command bundle106before being passed to the next routing node102c(shown as passed command bundle108after being passed through each routing node102once).

In one embodiment, the command bundle106is passed through each routing node102along the control path112, with each routing node102traversing the command bundle106to determine whether there are any commands that are able to be executed by a hardware module104connected to the routing node102.

In another embodiment, individual commands of the command bundle106may be selectively provided to different routing nodes102for parallel execution by one or more hardware module(s)104coupled to the different routing nodes concurrently or at nearly the same time based on slight differences in when the commands are actually received by the different routing nodes102and/or hardware modules104. In this embodiment, a pipeline router may be utilized to determine which hardware pipeline (and therefore which routing nodes102) to send the individual commands for execution thereof. The pipeline router is described in more detail with respect toFIG.3A.

Referring again toFIG.1, according to another embodiment, a load balancer may determine which hardware module104to send individual commands of the command bundle106for parallel execution by the different hardware modules104concurrently or at nearly the same time. In this embodiment, the different hardware modules104may be configured to execute the same type of command or similar command types, e.g., decrypt/encrypt, fetch/store, compress/decompress, etc. The load balancer is described in more detail with respect toFIG.3B.

Referring again toFIG.1, in an example, one of the routing nodes (e.g., routing node102a) may be configured to receive a particular type of command from the command bundle106to be processed and/or executed by hardware module104a. Responsive to routing node102adetermining that (a) the first command of command bundle106is not of the particular command type associated with hardware module104a, or (b) at least one argument used for executing the first command is not received in association with the first command, routing node102atransmits the first command from the command bundle106to a next routing node in the order of connection to the control path112(e.g., routing node102b).

According to one example, routing node102amay receive a second command of the command bundle106, and responsive to determining that (a) the second command is of the particular command type associated with hardware module104a, and (b) argument(s) (if any) used by the second command are received in association with the second command (e.g., via data path114and/or control path112), routing node102amay transmit the second command to hardware module104afor processing and/or execution by the hardware module104a. Upon successful execution, routing node102aand/or hardware module104amay modify the command bundle106based on execution of the second command.

In an approach, when a hardware module is associated with a command type, or vice versa, it indicates that the hardware module is configured to process and/or execute that particular type of command. This processing or execution may produce one or more results, end a process, start a process, trigger another command to execute, etc.

Many different command types are possible for execution by different hardware modules104. Each hardware module104may designed and configured to perform one type of command, or it may be configured to execute multiple command types that are similar, such as encrypt/decrypt, fetch/store, compress/decompress, etc. A non-exhaustive list of command types includes: an encrypt command, a decrypt command, an encode command, a decode command, a compress command, a decompress command, a fetch command, a store command, a configure command, a lookup command, a compare command, etc.

According to one approach, the command bundle106may be modified through one or more actions, with the possible actions being wide-ranging. For example, the command bundle106may be modified by refraining from transmitting the second command of the command bundle106to the next routing node in the order of connection to the control path112(e.g., routing node102b).

Other forms of modification of the command bundle106are possible, such as deletion or removal of the second command, modification of the second command, inclusion of one or more arguments within the command bundle106(e.g., as command data), inclusion of an implicit or explicit indicator (marker, note, pointer, flag, etc.) within the command bundle106denoting execution of the second command, storing a result of executing the second command in a dataset (e.g., on the data path114) associated with the second command of the command bundle106, storing an implicit or explicit indicator for the result in the command bundle106, addition of a data command in place of the second command in the command bundle106, addition of the data command in addition to the second command in the command bundle106, generating a new command bundle that includes no commands (a null bundle), etc.

A data command, as used herein, refers to a command that may be added to a command bundle which refers to a location (e.g., a FPGA memory address, CPU memory address, GPU memory address, etc.) to access a result of executing a command from the command bundle.

In another example, routing node102b, which is communicatively coupled to hardware module104bmay be configured to receive the command bundle106after it has passed through routing node102afrom control path112. Routing node102bis configured to traverse the command bundle106to determine if any commands in the command bundle106are of a command type associated with hardware module104b. For this example, a second command type is associated with hardware module104b.

Responsive to routing node102bdetermining that the command bundle106does not include any commands of the second command type associated with hardware module104b, routing node102btransmits the command bundle106, without modification as it was received from routing node102a, to a next routing node102in the hardware pipeline100(e.g., routing node102c).

In another example, responsive to routing node102bdetecting that command bundle106includes a specific command of the second command type, routing node102bwill determine whether the specific command uses any parameters. Each command may reference one or more parameters (e.g., a set of parameters) that are used in execution of the command. For example, a fetch command may need an address to find a particular file, or an encode command may need an argument to encode that is not present in the command itself (even if the encoding algorithm is present in the command). In order for such a command to be executed by a hardware module, each parameter must be available to the hardware module.

Sometimes, one or more of the parameters is not available. This may be due to the parameter not being determined yet through execution of a separate command, the parameter not being passed to the hardware module, a pointer to the parameter being faulty, outdated, or broken, the parameter failing to meet certain requirements of the command, etc. When this situation arises, the command is not able to be executed, and the command bundle106is passed to the next routing node102.

In an example, in response to routing node102bfailing to detect at least one parameter value in the set of parameters (and therefore not being able to process the related command from the command bundle106), the routing node102bmay transmit the command bundle106, as it was received without modification, to a next routing node102in the hardware pipeline100(e.g., routing node102c).

Hardware pipeline100may be designed to recycle or recirculate the passed command bundle108back to the beginning of the control path112once it has traversed through each routing node102in hardware pipeline100. In this way, the passed command bundle108will be passed back to routing node102aone or more times (the total number of recirculations), depending on a configuration of the hardware pipeline100.

In one embodiment, hardware pipeline100may be configured to attempt to process each command in the command bundle106(and any commands remaining in the passed command bundle108after traversing through the hardware pipeline100) until the earliest of: all commands have been processed, the command bundle106has been passed through hardware pipeline100a predetermined number of times (e.g., two times, three times, four times, five times, etc.), or a predetermined amount of time has elapsed (e.g., 100 microseconds, 10 milliseconds, 1 second, 10 seconds, 30 seconds, etc.) since the command bundle106was introduced to the hardware pipeline100, etc.

In one example, subsequent to transmitting the command bundle106to the last routing node102n, hardware pipeline100is configured to send the passed command bundle108back to routing node102a. Routing node102aprocesses the passed command bundle108in the same way that it processed command bundle106the first time. In the case where commands exist in the passed command bundle108after processing by routing node102a, routing node102awill pass the passed command bundle108to routing node102b.

Routing node102b, upon receiving the passed command bundle108(all commands remaining from command bundle106after passing along the control path112through hardware pipeline100), routing node102btraverses the passed command bundle108to detect a specific command of the second command type associated with hardware module104bwithin the passed command bundle108. This may be the same command of the second command type that was analyzed previously by routing node102b, but not processed due to one or more missing parameter values. When routing node102breceives the specific command this time, upon detecting that all values of the set of one or more values corresponding to the set of parameters for the specific command are available, routing node102bexecutes the specific command based on the set of one or more values. After executing the specific command from the passed command bundle108, routing node102bmodifies the passed command bundle108based on execution of the specific command and transmits the modified passed command bundle108to the next routing node along the control path112(e.g., routing node102c).

In one or more embodiments, the hardware pipeline100may include more or fewer components than the components illustrated inFIG.1. The components illustrated inFIG.1may be local to or remote from each other. The components illustrated inFIG.1may be implemented in hardware with or without the aid of software-defined rules. Each component may be used to accelerate multiple applications. Multiple components may be used to accelerate any single application. Operations described with respect to one component may instead be performed by another component.

Moreover, the hardware pipeline100may be leveraged in a common architecture for use by any accelerated application executing on a computer system. Hardware pipeline100may also respond to a common programming paradigm used by software developers to program the hardware pipeline100to perform desired compute functions (similar to CPUs and GPUs).

2.2. Command Bundle

FIG.2shows example command bundles for use with an accelerated hardware architecture (system). Any number of commands may be included in any single command bundle, and the order of the commands within the particular command bundles may be selected and/or determined using an application configured for optimizing the order of commands in a particular command bundle based on the arrangement of hardware modules in a particular system.

There are many aspects to consider when generating an arrangement of hardware modules in a particular system. Some of these aspects include, but are not limited to, a total number of hardware modules the particular system, a type of command associated with each hardware module, a number of hardware modules associated with the same type of command, the presence of load balancers, interfaces configured to choose from among several different pipelines (collection of routing nodes and associated hardware modules), number of recirculations allowed, etc. Each of these aspects is described in more detail herein.

The application may optimize the individual commands included in a command bundle along with an order for the included commands, in order to achieve a desired outcome from processing the command bundle using one or more particular processing pipelines. Moreover, each command comprises instructions or functions that are to be executed and/or processed, and each instruction or function may reference, utilize, and/or generate one or more arguments, parameters, outcomes, or values.

As shown, Command A202is first in command bundle216, followed by Command B204, Command C206, Command D208, Command E210, Command F212, and Command G214. Command bundle218begins with two instances of Command B222,224, followed by two instances of Command D226,228, one Command F230, and concludes with three instances of Command A232,234,236. Command bundle220repeats a pattern two times, such that Command F238, Command E240, and Command C242are followed by another pattern of Command F244, Command E246, and Command C248.

In an example, assume that each of these command bundles are provided to a particular pipeline250that includes an ordered set of hardware modules capable of processing commands in the following order: Command F—Command A—Command B—Command C—Command D. The architecture of the pipeline250is simplified as a series of modules in this diagram. However, each individual module comprise a routing node that is coupled to one or more hardware modules configured to process the specific command type shown for the module. For the pipeline250, each module, once it receives a command bundle, will traverse the command bundle until it reaches a command that it is configured to process. The module will process the command (is possible) and forward on the command bundle to the next module. The command bundle may be modified to indicate processing of a command in some instances. For the sake of these descriptions, once a module processes a command, the command will be removed from the command bundle.

In this example, for command bundle216, the first module252would traverse command bundle216until it reached Command F212and it would process that command. The first module252would also forward the command bundle216to the second module254, which would process the first command in command bundle216(Command A202) and forward on the command bundle216. The third module256would receive command bundle216from the second module254, and would traverse the command bundle216until it reached and processed the second command (Command B204). The third module256would also forward the command bundle216to the fourth module258. The fourth module258would traverse the command bundle216until it reached and processed the third command in command bundle216(Command C206). The fourth module258would also forward the command bundle216to the fifth module260. The fifth module260would traverse command bundle216until it reached the fourth command (Command D208) and it would process that command. No other modules are present in the pipeline250for processing commands, so the remaining commands in command bundle216(e.g., Command E210and Command G212) would remain unprocessed, no matter how many times the command bundle216was recirculated through the pipeline250.

Continuing with this example, for command bundle218, the first module252would traverse command bundle218until it reached the first Command F230and it would process that command. The first module252would also forward the command bundle218to the second module254, which would traverse the command bundle218until reaching and processing the first Command A232in command bundle218. The second module would also forward on the command bundle218to the third module256, which would receive command bundle218and process the first Command B222. The third module256would also forward the command bundle218to the fourth module258. The fourth module258would traverse the command bundle218and not encounter any commands that it could process, and pass the command bundle218to the fifth module260. The fifth module260would traverse command bundle218until it reached the first Command D226and it would process that command. No other modules are present in the pipeline250for processing commands, so the remaining commands in command bundle218(e.g., Command B224, Command D228, Command A234, and Command A236) would remain unprocessed unless the command bundle was passed through a recirculation to be processed again by pipeline250. After passing through pipeline250for a second time, only Command A236would remain in the bundle.

Sending command bundle220through pipeline250in this example would result in the following actions. The first module252would process the first Command F238and forward the command bundle220to the second module254, which would traverse the command bundle220without finding any commands to process. Therefore, the second module254would forward command bundle220unchanged to the third module256, which would also traverse the command bundle220without finding any commands to process, so it would forward the command bundle220to the fourth module258. The fourth module258would traverse the command bundle220to reach the first Command C242, process the command, and pass the command bundle220to the fifth module260. The fifth module260would traverse command bundle220and not find any commands to process, leaving Command E240, Command F244, Command E246, and Command C248in the command bundle220after a first pass through pipeline250. After passing through pipeline250for a second time, all that would remain in the command bundle220would be Command E240and Command E246, because there are no modules in the pipeline250capable of processing commands of type E.

2.3. System Overview

FIG.3Ashows a block diagram of an example system300having a pipeline router312in accordance with an embodiment. System300includes a signal interface302configured to split a command signal304into at least two components: a command bundle310which is provided to a control path306, and a data stream comprising associated data which is provided to a data path308. An output314is produced once commands of a command bundle310have been executed, and may include data from the control path306and/or the data path308, in various approaches.

The signal interface302may be implemented in hardware, software, or a combination of hardware and software. The signal interface302is configured to receive the command signal304and determine which portions of the command signal304include commands for processing that are packaged into the command bundle310, and which portions of the command signal304include data (e.g., user data, metadata, parameters, parameter values, etc.) which may be used to process the various commands in the command bundle310. The data stream is sent along the data path308separate from the command bundle310which is sent along the control path306.

According to one embodiment, multiple signal interfaces302may be included in a single system, with each signal interface302being coupled to its own control path306and data path306. In this way, the plurality of signal interfaces302may select to process a particular command signal304(in lieu of deferring for another signal interface to process the command signal304) based on a number of factors, including but not limited to, the availability of hardware pipeline(s), commands to be processed in the command signal304, arrangement of the hardware pipeline(s), etc.

In one embodiment, the control path306is configured to utilize a fixed size of argument (each command in a command bundle310), such as 16 bits, 32 bits, 64 bits, 128 bits, etc. In an alternate embodiment, the control path306is configured to utilize a variable size of argument (each command in a command bundle310), with a maximum argument size being selected by a designer or by default, such as 32 bits, 64 bits, 128 bits, 256 bits, 512 bits, etc.

In an embodiment, the data path308is configured to utilize a variable size of argument (data associated with commands in the command bundle310), with a maximum argument size being selected by a designer or by default, such as 32 bits, 64 bits, 128 bits, 256 bits, 512 bits, etc. In an alternate embodiment, the data path308is configured to utilize a fixed size of argument (data associated with commands in the command bundle310), such as 16 bits, 32 bits, 64 bits, 128 bits, etc.

According to an approach, the data path308is asynchronous to the control path306, such that the data portion of the command signal304may be transmitted along the data path308independently from the command bundle310being transmitted along the control path306, initially and after recirculating along the recirculation loop318.

Once the command bundle310is generated, it is provided to the control path306. In an embodiment, a pipeline router312receives the command bundle310prior to forwarding the command bundle310to a selected hardware pipeline316. The pipeline router312is implemented in hardware in one embodiment. In an approach, the pipeline router312may be implemented in hardware with configuration changes possible via software in another embodiment. According to another approach, the pipeline router312may be implemented in software.

The pipeline router312is configured to determine which hardware pipeline316from a group of hardware pipelines (e.g., hardware pipeline316a, hardware pipeline316b, hardware pipeline316c, . . . , hardware pipeline316n) is best suited for processing the commands in command bundle310. Each hardware pipeline316comprises an ordered series of modules (not shown) for processing commands. Each module includes a routing node coupled to one or more associated hardware modules for processing commands of a certain type, with any number of modules being possible in any particular hardware pipeline316(limited only by constraints on hardware architecture: physical space and layout, and a desired minimum time to traverse a hardware pipeline).

The pipeline router312may utilize the individual arrangements of each hardware pipeline316(which types of commands may be processed by components of the pipeline), knowledge of which hardware pipelines316are available for processing additional commands at any given time, which type of commands are included in the command bundle310, and an order of the commands in the command bundle310to make the determination of which hardware pipeline316to send a particular command bundle310. The choice of which hardware pipeline316to use for a particular command bundle310may also be used in choosing which hardware pipeline316to use for a next received command bundle310in an approach. The command bundle310may be split into multiple portions by the pipeline router312, with the portions being transmitted to different hardware pipelines316in an approach.

According to an embodiment, the pipeline router312(or some other suitable component of system300) may selectively provide individual commands of the command bundle310to different hardware pipelines316and/or routing nodes within specific hardware pipelines316to allow for parallel execution by different hardware modules associated with the different routing nodes concurrently or at nearly the same time (e.g., based on slight differences in when the commands are actually received by the different hardware modules).

In one embodiment, the routing nodes (and thus associated hardware modules for processing commands of certain types) within each particular hardware pipeline316are arranged in a particular order. In this embodiment, the pipeline router312is configured to select a particular hardware pipeline (e.g., hardware pipeline316ainstead of any of the other hardware pipelines316b,316c, . . . ,316n) to transmit the command bundle310based on one or more criteria. The criteria includes, but is not limited to, an order of commands in the command bundle310, command types of the commands in the command bundle310, metadata in the command bundle310and/or in the data path308, and availability of individual hardware pipelines316for processing commands. Once the pipeline router312selects the particular hardware pipeline (e.g., hardware pipeline316a), the command bundle310is transmitted to the particular hardware pipeline.

In an alternate embodiment, system300may include a single hardware pipeline316comprising an ordered series of modules, each module including a routing node coupled to one or more associated hardware modules for processing commands of a certain type. In this embodiment, no pipeline router312would be used. However, the signal interface302would still be present for splitting the command signal304into components for the control path306and data path308as described previously.

In an embodiment, a hardware pipeline316may include one or more storage devices (such as buffers, memories, registers, etc.). The storage device(s) are configured to store data for use by a routing node and/or hardware module within the hardware pipeline316. According to one embodiment, each set of routing node/hardware module(s) includes at least one storage device for use in processing commands of a command bundle310.

In an embodiment, the control path306may include a recirculation loop318which allows for a command bundle310to be sent back to the pipeline router312and/or a hardware pipeline316for continued processing after having been passed through a selected hardware pipeline. In this embodiment, the pipeline router312may be configured to perform additional tasks after transmitting the command bundle310to the selected hardware pipeline. For example, the pipeline router312may be configured to determine whether at least one command in the command bundle310has not been executed by a hardware module of the selected hardware pipeline. Also, responsive to determining that the at least one command in the command bundle310has not been executed after being returned along the recirculation loop318, the command bundle310may again be transmitted to at least one selected hardware pipeline316. The same hardware pipeline may be used in one embodiment. In another embodiment, one or more different hardware pipelines may be used for continued processing of the command bundle310, with or without the originally selected hardware pipeline.

Upon receiving the command bundle310at the pipeline router312from the recirculation loop318, the pipeline router312(or some other component of system300) is configured to determine a number of times that the command bundle310has been transmitted through the control path306(e.g., a selected hardware pipeline316). In response to determining that at least one command in the command bundle310has not been executed, and the number of times that the command bundle310has been sent through the control path306exceeds a configurable threshold (e.g., 2 times, 3 times, 5 times, 10 times, etc.), the pipeline router312generates an error indicating that processing of the command bundle310has failed.

In another embodiment, the pipeline router312(or some other component of system300) is configured to determine an amount of time that has elapsed since the command bundle310was transmitted through the control path306(e.g., a selected hardware pipeline) the first time. In response to determining that at least one command in the command bundle310has not been executed after receiving the command bundle310from the recirculation loop318, and that the elapsed amount of time exceeds a configurable duration threshold (e.g., 100 microseconds, 10 milliseconds, 1 second, 10 seconds, 30 seconds, etc. —the total amount of time allowed for a command bundle to complete processing including recirculation attempts), the pipeline router312generates an error indicating that processing of the command bundle310has failed. This approach is helpful to ensure that a command bundle310that may never complete processing is not repeatedly sent back through the control path306. The command bundle310may never complete processing due to some unforeseen issue with the command bundle310, the arrangement of the hardware pipeline(s)316, or both.

In an approach, the pipeline router312(or some other component of system300) is configured to determine an amount of time that has elapsed since the command bundle310was transmitted through the control path306(e.g., a selected hardware pipeline). In response to determining that the elapsed amount of time exceeds a configurable passthrough threshold (e.g., 100 microseconds, 10 milliseconds, 1 second, 10 seconds, 30 seconds, etc. —the amount of time allowed for a command bundle to complete processing once through), the pipeline router312may re-transmit the command bundle310back through the selected hardware pipeline or along another hardware pipeline. This approach is helpful to ensure that a command bundle310does not get “stuck” or slowed-down in a hardware pipeline and never or only very slowly completes processing, due to some unforeseen issue with the command bundle310, the arrangement of the hardware pipeline(s)316, or both.

In one example, each of the hardware modules associated with the routing nodes in a particular hardware pipeline316may be configured to execute a same command type (e.g., all hardware modules in hardware pipeline316cmay process fetch and/or store commands). Moreover, the pipeline router312may be configured to perform load balancing across each the plurality of hardware modules associated with the plurality of routing nodes in hardware pipeline316c. Load balancing ensures that different command bundles310and/or individual commands within command bundles310are load-balanced across the particular hardware modules in hardware pipeline316cto more efficiently utilize the fetch command processing of the hardware pipeline316c.

FIG.3Bshows a block diagram of an example system320having a load balancer322in accordance with an embodiment. System320includes a routing node324communicatively coupled to a plurality of hardware modules326(e.g., hardware module326a, hardware module326b, . . . , hardware module326n). Each hardware module326is coupled to a data path308for accessing data associated with the various commands of the command bundle310.

An output314is produced once commands of a command bundle310have been executed, and may include data from the control path306and/or the data path308, in various approaches. A recirculation loop318is provided for recycling the command bundle310back to the routing node324(or the load balancer322in some implementations) for processing by the various hardware modules326one or more additional times. The recirculation loop318may be used when at least one command remains in the command bundle310after being passed through the various hardware modules326.

In one implementation, the load balancer322may be integrated into the routing node324. In other words, the routing node324may be configured to perform load balancing across the plurality of hardware modules326communicatively coupled thereto. Load balancing may account for any number of factors or aspects. These factors or aspects may be related to any of the hardware modules326, the command bundle310, an order of commands within the command bundle310, the type of commands within the command bundle310, a number of recirculations performed and/or allowed, etc.

Some hardware modules326are configured to execute more than one command type. However, the multiple command types that are able to be executed typically are related in some way, such as encrypt and decrypt, fetch and store, compress and decompress, etc. In this way, hardware modules326may execute different command types, but the command types are related (e.g., similar commands).

In system320, each hardware module326is configured to execute the same or similar commands, and the routing node324has knowledge of the specific command(s) executable by the plurality of hardware modules326. The command bundle310is received by routing node324, which determines which commands in the command bundle310are executable by the various hardware modules326. These selected commands are sent to the load balancer322, which distributes the selected commands across the plurality of hardware modules326to be executed in parallel. In this way, multiple commands may be executed concurrently or at nearly the same time (based on slight differences in when the commands are actually received by the different hardware modules326).

According to one approach, a plurality of routing nodes may be arranged in a particular order within a hardware pipeline in accordance with software-defined rules. A composer application associated with the command-aware hardware architecture may adhere to the software-defined rules in choosing and/or selecting how to arrange individual routing nodes within a particular hardware pipeline. The software-defined rules may include rules for managing the number of routing nodes (and associated at least one hardware module), rules for positioning routing nodes within a hardware pipeline, rules associated with load-balancing and hardware pipeline routing, etc.

The rules for positioning routing nodes may include, but are not limited to, which types of routing nodes (dictated by a type of command that a hardware module associated with a routing node is configured to process) may or must be positioned next to one another, which types of routing nodes may or must be positioned before another type of routing node, which types of routing nodes may be positioned after another type of routing node, etc.), how many of the same type of routing nodes may be positioned in series, etc.

The rules for managing the number of routing nodes may include, but are not limited to, a total number of routing nodes in a particular hardware pipeline, a minimum number of routing nodes in any hardware pipeline, a number of routing nodes that may be repeated in series, etc.

The rules associated with load-balancing may include, but are not limited to, distributing processing loads according to a scheme or metric across multiple hardware pipelines, and distributing loads across hardware modules which execute the same or similar command type within a single hardware pipeline. When distributing processing loads across multiple hardware pipelines, a load-balancer may ensure that each hardware pipeline is utilized in accordance with the scheme or metric over a certain period of time, avoiding busy or unavailable hardware pipelines when selecting which hardware pipeline to send a command bundle, etc. When distributing loads across hardware modules which execute the same or similar command type, a load-balancer may ensure that each hardware module is utilized approximately equally, that loads are directed to available hardware modules, that loads are directed with knowledge of ordering concerns within the command bundle, etc.

According to one embodiment, a cluster of systems300and/or320may be implemented as a single unit, controlled to operate together to process commands of varying types. This arrangement is helpful when the compute functions need to be distributed across multiple FPGAs and/or ASICs.

An application that a designer desires to execute in an accelerated manner, either using ASICs, FPGAs, CPUs, GPUs, etc., may be implemented using the general architecture of system300and/or320. This provides the designer with the ability to aggregate individual instructions and functions from the application into a series of command bundles (a program) which may be made to specify the input and output interfaces of the program, the compute modules (each comprising a routing node and associated hardware module(s)), a series of commands that are executed in the program, an order in which the commands are executed, and a relationship and dependency between each command.

In an approach, the system300and/or320and software controlling the system300and/or320do not need to be modified every time a new compute function is introduced or an existing compute function is changed. This allows a designer to generate FPGA accelerated applications using a common architecture. In one approach, when utilizing an FPGA-based hardware architecture, system300and/or320provides the ability to leverage re-programmability of FPGAs to support different sets of compute functions for different applications, and make changes that cause the capability of the processor architecture to change as desired.

Usually, redesigning an FPGA may take significant amounts of time (e.g., multiple weeks or months), and a lot of effort and resources may be needed to make such changes. When the FPGA is redesigned, the software programming interface often changes, which requires a change to the software stack.

However, a software-based composer application provided with system300and/or320is configured to build a new system architecture on-demand. This new system architecture accounts for certain characteristics of the FPGA being used for compute functions in system300and/or320, including the vendor of the FPGA platform, the specific FPGA platform, capability of the specific FPGA (e.g., features, an order to instantiate the features, and order of execution for the features), and a bandwidth of the FPGA (e.g., speed provided by each feature and the overall FPGA).

In one embodiment, the composer application receives input from the designer, automatically configures the parameters and assembles the required features in an appropriate fashion to dynamically build a system that comprises a signal interface302, control path306, data path308, and at least one hardware pipeline on the defined FPGA platform. In this way, a truly dynamic hardware computing platform is possible, and the configurable hardware platform may be repurposed on-demand to serve novel and current needs of the end-user and specific application tasks.

3. EXAMPLE EMBODIMENTS

A detailed example is described below for purposes of clarity. Components and/or operations described below should be understood as one specific example which may not be applicable to certain embodiments. Accordingly, components and/or operations described below should not be construed as limiting the scope of any of the claims.

3.1 Hardware Routing Mesh

FIGS.4A-4Cshow a hardware routing mesh400and example pipelines chosen for processing commands. The hardware routing mesh400comprises a plurality of hardware modules configured to process different command types. For simplicity, only three command types are included in the hardware routing mesh400: Command type A, Command type B, and Command type C. The connections between the various hardware modules are for example only, and any interconnections, any number of hardware modules, any specific commands and command types, and any arrangement of the hardware modules may be used in a hardware routing mesh in various approaches.

FIG.4Aalso shows two example command bundles. Command bundle434comprises, in order: Command A—Command B—Command C—Command B—Command C—Command B—Command A. Command bundle436comprises, in order: Command B—Command B—Command A—Command B—Command C—Command C—Command A. The hardware routing mesh400is capable of being used in any desired arrangement for selecting a hardware pipeline therefrom, as long as a connection exists between the desired hardware modules, and a hardware module is not used twice in a single pipeline.

FIG.4Bshows an example hardware pipeline chosen through hardware routing mesh400intended to optimize processing of command bundle434. The selected hardware pipeline starts with hardware module402(configured to process command type A), followed by hardware module404(configured to process command type B), hardware module406(configured to process command type C), hardware module408(configured to process command type C), hardware module422(configured to process command type B), hardware module420(configured to process command type C), hardware module426(configured to process command type B), and ending with hardware module430(configured to process command type A). The individual hardware modules that are used to process each command in command bundle434are indicated with numbers beside the commands in the command bundle434. Of note here is that hardware module408is not used to process any commands in command bundle434, but it is included in the hardware pipeline because it creates the shortest route through the hardware routing mesh400that includes each required hardware module in the required order. There are other pipeline configurations possible that will also result in all commands in command bundle434being processed, and they may include the same number of hardware modules (8) or have more hardware modules.

A composer application will attempt to optimize the selection of the hardware pipeline(s) through any given hardware routing mesh based on processing request it receives that details what functions are to be processed.

FIG.4Cshows an example hardware pipeline chosen through hardware routing mesh400intended to optimize processing of command bundle436. The selected hardware pipeline starts with hardware module404(configured to process command type B), followed by hardware module414(configured to process command type B), hardware module418(configured to process command type A), hardware module410(configured to process command type B), hardware module412(configured to process command type C), hardware module428(configured to process command type C), and ending with hardware module424(configured to process command type A).

The individual hardware modules that are used to process each command in command bundle436are indicated with numbers beside the commands in the command bundle436. It is noted that the exact amount of hardware modules are included in the chosen hardware pipeline as the number of commands in command bundle436—an optimal solution. There are other pipeline configurations possible that will also result in all commands in command bundle436being processed, and they may include the same number of hardware modules (7) or have more hardware modules.

The examples shown inFIGS.4A-4Cillustrate how the same hardware routing mesh400may be configured to perform different functions in a different order based on a pipeline selection of the hardware modules included in the hardware routing mesh400. The selection of the hardware pipeline(s) by the composer application may consider many factors in making this decision, including but not limited to, a current arrangement of the hardware routing mesh, number and types of commands in a command bundle, presence or absence of a recirculation loop, number and position of hardware modules capable of processing each command type, etc.

3.2 Method for Processing a Command

FIG.5illustrates an example method500for processing a command from a command bundle using a routing node in accordance with one or more embodiments. One or more operations illustrated inFIG.5may be modified, rearranged, or omitted all together. Accordingly, the particular sequence of operations illustrated inFIG.5should not be construed as limiting the scope of one or more embodiments.

In addition, method500may be implemented using a hardware routing mesh that includes a plurality of routing nodes. Each routing node is associated with one or more hardware modules. Each hardware module is configured to process a certain type of command dependent on the individual hardware module (e.g., different command types may be processed by the different hardware modules in the hardware routing mesh).

In operation502, a first routing node in a hardware pipeline of a hardware routing mesh receives a first command of a command bundle. The command bundle is streamed through the plurality of routing nodes of the hardware pipeline. Moreover, as commands in the command bundle are processed and/or executed, the command bundle is modified based on such execution of commands.

In operation504, the first routing nodes determines whether the first command is of a particular type that a first hardware module communicatively coupled to the first routing node is configured to process. In response to a “Yes” determination indicating that the first command is of the particular type, method500continues to operation506; otherwise, method500jumps to operation512.

In operation506, the first routing nodes determines whether all arguments used for executing the first command are available (if any arguments are specified by the first command). In response to a “Yes” determination indicating that all arguments are available, method500continues to operation508; otherwise, method500jumps to operation512.

In operation508, the first routing node transmits the first command to the first hardware module in order for the first hardware module to execute and/or process the first command. In one embodiment, the first routing node may also transmit any arguments necessary for executing the first command to the first hardware module, with the arguments being obtained from a data path and/or from metadata associated with commands in the command bundle.

In operation510, the first routing node modifies the command bundle based on execution of the first command. In one embodiment, modifying the command bundle may include, at a minimum, refraining from transmitting the first command of the command bundle to the second routing node. This is performed in order to ensure that the first command is not repeated by any other hardware modules of the hardware pipeline.

According to an approach, the command bundle may be modified to include an indicator (e.g., pointer, link, marker, flag, etc.) denoting execution of the first command. The indicator may be placed anywhere in the command bundle, such as in metadata associated with the command bundle, in a position where the first command is or was located in the command bundle, at an end or beginning of the command bundle, etc.

In another approach, the command bundle may be modified to store a result of executing the first command in a dataset associated with the first command of the command bundle. The dataset may be stored to the data path, in the command bundle, and/or in a memory device associated with the first hardware module, the first routing node, and/or the hardware pipeline.

The result may be an outcome, argument, parameter, value, or some other data that results from execution or processing of the first command. For example, if the first command is a fetch command, the result is the data that the first command instructs to fetch from storage.

In another approach, the command bundle may be modified to store an indicator for the result in the command bundle. The indicator (e.g., pointer, link, marker, flag, etc.) may directly or indirectly point to a location where the result is stored.

In other approaches, the command bundle may be modified to remove the first command from the command bundle, and/or add a data command in place of the first command in the command bundle. The data command may refer to a location to access the result of executing the first command.

In another approach, the command bundle may be modified to add the data command in addition to the first command in the command bundle.

In yet another approach, the command bundle may be modified by generating a new command bundle that includes no commands (e.g., an empty command bundle) that may replace or be sent along the control path in addition to the command bundle.

In operation512, responsive to determining that (a) the first command is not of the particular command type associated with the first hardware module, or (b) at least one argument used for executing the first command is not available, the first routing node transmits the first command of the command bundle to a second routing node in the hardware pipeline. The first command is forwarded on down the hardware pipeline because the first routing node is not able to process the first command at this time.

3.3 Method for Traversing a Command Bundle with a Routing Node

FIG.6illustrates an example method600for traversing a command bundle with a routing node in accordance with one or more embodiments. One or more operations illustrated inFIG.6may be modified, rearranged, or omitted all together. Accordingly, the particular sequence of operations illustrated inFIG.6should not be construed as limiting the scope of one or more embodiments.

In addition, method600may be implemented using a hardware routing mesh that includes a plurality of routing nodes. Each routing node is associated with one or more hardware modules. Each hardware module is configured to process a certain type of command dependent on the individual hardware module (e.g., different command types may be processed by the different hardware modules in the hardware routing mesh).

In operation602, a particular routing node in a hardware pipeline of a hardware routing mesh receives a command bundle. The command bundle may be passed by a routing node in the hardware pipeline, forwarded by a pipeline router, received through a recirculation loop, or obtained in some other way through the hardware routing mesh.

The command bundle includes an ordered set of commands, with each command provided instructions and/or functions to be processed and/or executed. In some instances, a command may also include or make reference to one or more arguments, parameters, and/or values that are used to process/execute the command. The command bundle is streamed through the plurality of routing nodes of the hardware pipeline. Moreover, as commands in the command bundle are processed and/or executed, the command bundle is modified based on such execution of commands.

In operation604, the particular routing node traverses the command bundle to determine whether the command bundle includes any commands of a particular command type. Traversing the command bundle allows the particular routing node to examine a type of command for each command in the command bundle. In this way, the particular routing node is able to determine whether the command bundle includes any commands of the particular command type that one or more hardware modules associated with the particular routing node are configured to process and/or execute. If there are no commands of a type that can be processed and/or executed by the particular routing node's hardware module(s), then the command bundle may be passed on or ignored by the particular routing node.

The method600continues to operation606in response to a “Yes” determination that the command bundle includes at least one command of the particular command type; otherwise, method600jumps to operation614.

In operation606, the particular routing node determines whether all values are available from a set of one or more values that correspond to a set of parameters for any specific command of the particular command type. Being available indicates that the values have been received by the particular routing node, received by the associated hardware module(s), the particular routing node is aware of a location to obtain the values, and/or the associated hardware module(s) are aware of the location to obtain the values.

Each command in the command bundle that is of the particular command type is analyzed in this way to determine whether all values are available for at least one of the commands of the particular command type that is present in the command bundle.

The method600continues to operation608in response to a “Yes” determination that all values are available from the set of one or more values that correspond to the set of parameters for the specific command; otherwise, method600jumps to operation614.

In operation608, the particular routing node sends the specific command to one or more associated hardware modules to process and/or execute the specific command. In an embodiment, the set of one or more values that correspond to the set of parameters for the specific command are utilized to process and/or execute the specific command, e.g., the specific command is executed based on the set of one or more values. Moreover, a result may be produced based on the one or more associated hardware modules processing and/or executing the specific command.

In an approach, the result may be stored to a memory device of the particular routing node, a memory device associated with the one or more associated hardware modules, in a data set on the data path, in a data command, etc.

In operation610, the first routing node modifies the command bundle based on execution of the specific command. In one embodiment, modifying the command bundle may include, at a minimum, refraining from transmitting the specific command of the command bundle to the next routing node in the hardware pipeline. This is performed in order to ensure that the specific command is not repeated by any other hardware modules of the hardware pipeline.

According to an approach, the command bundle may be modified to include an indicator (e.g., pointer, link, marker, flag, etc.) denoting execution of the specific command. The indicator may be placed anywhere in the command bundle, such as in metadata associated with the command bundle, in a position where the specific command is or was located in the command bundle, at an end or beginning of the command bundle, etc.

In another approach, the command bundle may be modified to store a result of executing the specific command in a dataset associated with the specific command of the command bundle. The dataset may be stored to the data path, in the command bundle, and/or in a memory device associated with the hardware module(s), the particular routing node, and/or the hardware pipeline.

The result may be an outcome, argument, parameter, value, or some other data that results from execution or processing of the specific command. For example, if the specific command is a fetch command, the result is the data that the specific command retrieves.

In another approach, the command bundle may be modified to store an indicator for the result in the command bundle. The indicator (e.g., pointer, link, marker, flag, etc.) may directly or indirectly point to a location where the result is stored.

In other approaches, the command bundle may be modified to remove the specific command from the command bundle, and/or add a data command in place of the specific command in the command bundle. The data command may refer to a location to access the result of executing the specific command.

In another approach, the command bundle may be modified to add the data command in addition to the specific command in the command bundle.

In yet another approach, the command bundle may be modified by generating a new command bundle that includes no commands (e.g., an empty command bundle) that may replace or be sent along the control path in addition to the command bundle.

In operation612, the first routing node transmits the modified command bundle to a next routing node in the hardware pipeline. The command bundle progresses along the control path to reach each routing node in the hardware pipeline.

In operation614, the particular routing node transmits the command bundle, without modification, to the next routing node in the hardware pipeline. The particular routing node forwards on the command bundle without processing any commands therefrom in response to determining that the command bundle does not include any commands of the particular command type, or in response to failing to detect at least one value in the set of one or more values corresponding to the set of parameters for the specific command.

Variations of the disclosed embodiments are also possible, and the explicit description thereof in this document is not required in order to provide a person having ordinary skill in the art with the ability to conceive of such variations when reading the present descriptions.

In the foregoing specification, embodiments of the invention have been described with reference to numerous specific details that may vary from implementation to implementation. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. The sole and exclusive indicator of the scope of the invention, and what is intended by the applicants to be the scope of the invention, is the literal and equivalent scope of the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction.

6. MISCELLANEOUS; EXTENSIONS

Embodiments are directed to a system with one or more devices that include a hardware processor and that are configured to perform any of the operations described herein and/or recited in any of the claims below. In an embodiment, a non-transitory computer readable storage medium comprises instructions which, when executed by one or more hardware processors, causes performance of any of the operations described herein and/or recited in any of the claims.

Any combination of the features and functionalities described herein may be used in accordance with one or more embodiments. In the foregoing specification, embodiments have been described with reference to numerous specific details that may vary from implementation to implementation. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. The sole and exclusive indicator of the scope of the invention, and what is intended by the applicants to be the scope of the invention, is the literal and equivalent scope of the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction.

7. HARDWARE OVERVIEW

According to one embodiment, the techniques described herein are implemented by one or more special-purpose computing devices (i.e., computing devices specially configured to perform certain functionality). The special-purpose computing devices may be hard-wired to perform the techniques, or may include digital electronic devices such as one or more application-specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or network processing units (NPUs) that are persistently programmed to perform the techniques, or may include one or more general purpose hardware processors programmed to perform the techniques pursuant to program instructions in firmware, memory, other storage, or a combination. Such special-purpose computing devices may also combine custom hard-wired logic, ASICs, FPGAs, or NPUs with custom programming to accomplish the techniques. The special-purpose computing devices may be desktop computer systems, portable computer systems, handheld devices, datacenter servers, networking devices or any other device that incorporates hard-wired and/or program logic to implement the techniques.

For example,FIG.7is a block diagram that illustrates a computer system700upon which an embodiment of the invention may be implemented. Computer system700includes a bus702or other communication mechanism for communicating information, and a hardware processor704coupled with bus702for processing information. Hardware processor704may be, for example, a general purpose microprocessor.

Computer system700also includes a main memory706, such as a random access memory (RAM) or other dynamic storage device, coupled to bus702for storing information and instructions to be executed by processor704. Main memory706also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor704. Such instructions, when stored in non-transitory storage media accessible to processor704, render computer system700into a special-purpose machine that is customized to perform the operations specified in the instructions.

Computer system700further includes a read only memory (ROM)708or other static storage device coupled to bus702for storing static information and instructions for processor704. A storage device710, such as a magnetic disk or solid state disk, is provided and coupled to bus702for storing information and instructions.

Computer system700may be coupled via bus702to a display712, such as a liquid crystal display (LCD), plasma display, electronic ink display, cathode ray tube (CRT) monitor, or any other kind of device for displaying information to a computer user. An input device714, including alphanumeric and other keys, may be coupled to bus702for communicating information and command selections to processor704. Alternatively or in addition, the computer system700may receive user input via a cursor control716, such as a mouse, a trackball, a trackpad, a touchscreen, or cursor direction keys for communicating direction information and command selections to processor704and for controlling cursor movement on display712. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane. The display712may be configured to receive user input via one or more pressure-sensitive sensors, multi-touch sensors, and/or gesture sensors. Alternatively or in addition, the computer system700may receive user input via a microphone, video camera, and/or some other kind of user input device (not shown).

Computer system700may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system causes or programs computer system700to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system700in response to processor704executing one or more sequences of one or more instructions contained in main memory706. Such instructions may be read into main memory706from another storage medium, such as storage device710. Execution of the sequences of instructions contained in main memory706causes processor704to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

The term “storage media” as used herein refers to any non-transitory media that store data and/or instructions that cause a machine to operate in a specific fashion. Such storage media may comprise non-volatile media and/or volatile media. Non-volatile media includes, for example, solid-state or magnetic disks, such as storage device710. Volatile media includes dynamic memory, such as main memory706. Common forms of storage media include, for example, a floppy disk, a flexible disk, hard disk, solid state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a programmable read-only memory (PROM), and erasable PROM (EPROM), a FLASH-EPROM, non-volatile random-access memory (NVRAM), any other memory chip or cartridge, content-addressable memory (CAM), and ternary content-addressable memory (TCAM).

Storage media is distinct from but may be used in conjunction with transmission media. Transmission media participates in transferring information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus702. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor704for execution. For example, the instructions may initially be carried on a magnetic disk or solid state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a network, via a network interface controller (NIC), such as an Ethernet controller or Wi-Fi controller. A NIC local to computer system700can receive the data from the network and place the data on bus702. Bus702carries the data to main memory706, from which processor704retrieves and executes the instructions. The instructions received by main memory706may optionally be stored on storage device710either before or after execution by processor704.

Computer system700also includes a communication interface718coupled to bus702. Communication interface718provides a two-way data communication coupling to a network link720that is connected to a local network722. For example, communication interface718may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface718may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface718sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link720typically provides data communication through one or more networks to other data devices. For example, network link720may provide a connection through local network722to a host computer724or to data equipment operated by an Internet Service Provider (ISP)726. ISP726in turn provides data communication services through the world wide packet data communication network now commonly referred to as the “Internet”728. Local network722and Internet728both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link720and through communication interface718, which carry the digital data to and from computer system700, are example forms of transmission media.

Computer system700can send messages and receive data, including program code, through the network(s), network link720and communication interface718. In the Internet example, a server730might transmit a requested code for an application program through Internet728, ISP726, local network722and communication interface718. The received code may be executed by processor704as it is received, and/or stored in storage device710, or other non-volatile storage for later execution.