text:
|Publication number
|Publication type
|Application number
|Publication date
|Aug 10, 2010
|Filing date
|Apr 9, 2004
|Priority date
|Apr 9, 2003
|Fee status
|Also published as
|Publication number
|Gary Charles Berkowitz, Charles Christopher Wurtz
|Original Assignee
|Gary Charles Berkowitz, Charles Christopher Wurtz
|Export Citation
|BiBTeX, EndNote, RefMan
|Patent Citations (31), Non-Patent Citations (6), Referenced by (34), Classifications (14), Legal Events (1)
|External Links: USPTO, USPTO Assignment, Espacenet
This application incorporates by reference, in whole, the provisional application:
This application incorporates by reference, in whole, as a partial embodiment of some of the elements of the virtual supercomputer, the prior filed co-pending application:
Not Applicable
Not Applicable
1. Technical Field of Endeavor
The present invention is generally directed to the field of computing and more specifically to the field of information processing, and even more specifically, to the field of high-demand, high-performance, and supercomputing.
2. Description of the Related Art
The ability to use computers to process extremely complex or large amounts of stored information and derive new useful information from that information previously stored has assumed an important role in many organizations. The computer-aided methods used to store and derive information vary, but the vast majority of such methods depend on a general purpose computing hardware architecture. Accordingly, the potential to craft an optimal solution to a computing problem is limited by a static hardware architecture that is optimized not for any specific computing task, but rather to provide an acceptable level of processing ability over a wide and disparate range of computing tasks.
Attempts to create optimal solutions to solve specific and complex information processing tasks have focused on creating hardware architectures designed to exploit various features of the information to be processed so that such processing can be performed in an optimal manner. Hardware devices containing specialized vector processing units are one such example. Software written for such hardware formats the information into a form that takes advantage of the hardware's specialization, thus creating a computing environment that is tailored to the specific problem at hand. Such tailored solutions are usually implemented on high-end supercomputing hardware architectures with specialized software. Consequently, this approach is prohibitively expensive for most organizations, often costing millions of dollars. Additionally, once created, tailored solutions of this type are only suitable for a specific problem or class of problems.
The software written to solve specific high-performance computing problems is necessarily constrained by the features of the hardware upon which such software runs. When such software is in machine-readable form, it is tightly coupled to a specific architecture upon which it will run. Further, the underlying hardware machine architecture is almost always static, and only reconfigurable (and only partially so) in a few non-commercial machines not widely available. Even the so-called grid (or network or large-cluster) computing approaches, which rely on large numbers of interconnected physical or virtual machines, are still constrained by running on a few different types of conventional processors. While the topology of the network can be configurable in such approaches, the architecture of the underlying processors is static, and thus not tailored to the problem at hand.
The concept of a virtual supercomputer addresses these shortcomings. The virtual supercomputer provides a conceptual, reconfigurable hardware architecture for high-performance machine-readable software. The conceptual hardware architecture masks the actual underlying hardware from the machine-readable software, and exposes to the software a virtual machine reconfigurable for the problem at hand. The virtual supercomputer thus provides to the software the operations needed for optimal processing, unconstrained by the overhead associated with those hardware operations of the underlying machine that are not relevant to the task. This not only speeds the computing required for the problem, but also importantly, it dramatically speeds the process of software application development, as the developer can write program code to a machine that directly processes operations specifically optimized for the problem to be solved.
The virtual supercomputer translates the software instructions from the format for the virtual machine into a format that a particular underlying hardware architecture can process. Each specific hardware architecture must have a specific virtual machine associated with it. Thus, software for the virtual supercomputer can run on a wide variety of hardware architectures, because the virtual machine for each specific hardware architecture provides the same conceptual hardware architecture for software developers. Therefore, a large investment in a supercomputer or supercomputing cluster, with attendant maintenance and obsolescence issues, is avoided. Further, unlike a grid or conventional network computing system, which increases power in a brute-force manner by simply adding more processors, each virtual machine in a virtual supercomputer network has an internally configurable architecture, thus magnifying the power of the virtual supercomputer to provide a tailored solution.
One embodiment of some portions of the virtual supercomputer is described in the pending application Knowledge-based e-catalog procurement system and method, listed in the CROSS-REFERENCE section of this application.
The present invention solves the previously mentioned disadvantages as well as others. In accordance with the teachings of the present invention, a computer-implemented method, apparatus and system is provided for crafting high-performance information processing solutions that are able to be tailored to specific problems or classes of problems in a way that such tailored solutions will perform on a variety of hardware architectures while retaining the benefits of a tailored solution that is designed to exploit the specific information processing features and demands of the problem at hand.
The present invention provides a reconfigurable virtual machine environment upon which a tailored solution to a specific problem (including a class of problems) is crafted. Additionally, an operating system for such a virtual machine is included. The information to be processed for a problem is encoded into a solution-space, or manifold of nodes, where a node can be any kind of data structure, and the nodes may be independent (point clouds), or connected in any kind of topology, such as an acyclic directed graph (ACG) structure, a balanced tree, or other suitable data representation. This data representation is specifically constructed to closely match the architecture of the problem to be solved and the information to be processed. By exploring the data representation, the information comprising the problem is processed, and various possible solutions to the problem are generated and evaluated. The identified solution is not necessarily the optimal solution to the problem, but is sufficiently accurate and robust to be useful. The exploration of the data representation is performed in a controlled manner to locate a solution.
In one embodiment of the present invention, the virtual supercomputer operates on a single hardware processor and provides a software environment in which tailored solutions to multiple problems and/or problem classes can be created. In another embodiment of the present invention, the virtual supercomputer operates on a distributed interconnected network of hardware processors. Such processors may or may not be all of the same type. In this second embodiment, the advantages of additional computing resources and concurrent processing can be exploited to find a solution in a highly efficient manner.
Throughout, a synonym sometimes used for the present invention (virtual supercomputer) is the acronym NVSI (Netcentric Virtual Supercomputing Infrastructure).
The accompanying drawings, which are incorporated in and form part of the specification, illustrate an embodiment of the present invention and, together with the detailed description, serve to explain the principles of the invention.
In a preferred embodiment of the present invention, shown in
A problem domain-specific application requests specific processing tasks be performed for it by the virtual operating system running on the NVSI virtual machine (VM). These processing requests take the form of function calls that are defined by the virtual supercomputer's application programming interface (API). The architecture does allow for an embodiment in which direct calls to the VM are made by the Domain Application.
The virtual operating system (NVSI-OS) is composed of multiple layers containing a plurality of sub-components. The uppermost layer contains the OS managers. The managers coordinate various aspects of the creation of the solution space and the operation of the virtual supercomputer. Managers manage various engines and can invoke the operation of any set of engines to accomplish a task. The next layer contains engines, daemons, and a toolbox. The engines implement low-level machine instructions to send to the virtual machine and generate code that will activate the virtual machine. Daemons are background processes responsible for such tasks as reconfiguring the data representation, garbage collection, and memory recapture. An example would be pruning of unused or outdated branches in a tree manifold by the navigation engine (see below). The toolbox is a collection of routines that are frequently called by the managers. To accomplish certain frequently preformed tasks, a manager has the option of issuing an instruction to an engine or instead making a call to the toolbox.
The solution space is the collection of nodes or other data formats that are interconnected in such a way as to construct a data representation, or manifold, with input data encoded into its topology. One possible embodiment for such a data representation is an acyclic directed graph. Other possible embodiments include, but are not limited to: independent point-clouds, ordered sets of points, cyclic graphs, balanced trees, recombining graphs, meshes, lattices and various hybrids or combinations of such representations. Each node represents one point in the data representation that is implemented using a data structure. The topology of the data representation is determined by the interconnections among the data structures. A node contains data in various forms, depending on the particular problem to be solved. Choices from among possible data representations are made based upon the attributes of the particular problem to be solved. Data contained in a node can be in the forms of numeric tags, character tags, boolean flags, numeric values, character values, objects IDs, database-record IDs, simple arrays, variable-density multidimensional arrays, symbolic functions, mathematical functions, connection pointers to other nodes, function pointers, lookup-table list pointers, linked-lists, or even pointers to other solution spaces or data representations.
The instantiation engine (IE) provides instructions for the instantiation unit (IU) that creates and deletes nodes (the IU and other machine units are shown in
The configuration engine (CE) modifies a data representation(s) to create a topology tailored to the problem at hand. When creating this topology, the CE chooses from among a plurality of available topologies and modifies a chosen topology or topologies to suit the given problem. The CE then stores the chosen data representation parameters, and hardware configuration parameters, into the SCU.
The virtual operating system, including its component parts, interacts with the VM via the virtual assembler. The virtual assembler is analogous to a conventional assembler or compiler in that it converts function calls written in a high-level programming language into commands that the machine can understand and process. In this case, the commands are in a format the virtual machine can process.
The NVSI virtual machine (VM) interacts with the platform drivers. The platform drivers allow the virtual machine to interact with the operating system resident on the host computer. The platform drivers interact with one or more underlying hardware platform CPUs via a platform assembler, which converts commands from virtual machine-level function calls to commands that the platform-specific operating system and hardware can understand and process.
The virtual operating system has the ability to create multiple threads to perform tasks concurrently. When a new thread is created, a new virtual central processing unit (VCPU) is created along with the thread. Newly created VCPUs are not complete copies of the entire virtual machine. VCPUs contain only the components necessary for their respective processing tasks, such as the IU, PU, and NU. Certain components of the VM, such as the index memory, data memory, the configuration unit, and the network control unit (comprising the backbone 'core' of a CPU), are not typically duplicated in threads. The resources and services provided by such components are shared among the other components of the virtual supercomputer.
A functional block diagram of the components and interconnections within the virtual machine (NVSI Virtual Machine, as denoted by the bold-bordered box in
The Solution-space Configuration Unit (SCU) contains the index base register (IBR) stack, the index-memory allocation and data-memory allocation registers (IMAR, DMAR), the node data-structure definition register (DDR), the data definition array (DDA) memory, the field type (FT) table, the number of nodes register (NNR), the data definition count register (DDCR), and the parameter configuration register (PCR). The SCU is where the configuration structures of the virtual machine are stored. The PCR contains information that defines various attributes of the virtual machine by defining the structure of the data words used. This configuration can be altered by users or an application program at startup, or even during runtime execution.
The IBR stack is a set of IBRs that provides an indexed addressing system for memory access. Each virtual register stores a base address that specifies a boundary for a segment of the virtual supercomputer's memory space. Offsets may be calculated by taking this base address value and adding to it the value from the virtual node address (VNA) field of the node index word (IW) stored.
The DDA is a table of data-structure definition words (DDW), each identified by a unique integer data definition number (DDN). When a 'store data definition word' instruction is executed, if the DDN indicates that the DDW is new, the word is written into an available free memory location in the DDA. If the DDN indicates the word is not new, the previous version of the DDW is overwritten with the new version. The DDW to write into the table is located in the DDR.
The FT table in the SCU stores a list of preset data word field types, such as tag, flag, character, integer, fixed-point, floating-point, function pointer, node pointer, and list pointer. This table defines the valid field types that may be contained in a DDW (and may be extended via settings in the PCR).
The NNR is a virtual register that stores the current count of non-null nodes. It assists in the numbering and creation of new nodes as such nodes are instantiated, and serves effectively as a measure of the size of the solution space.
The DDCR is a virtual register contained within the SCU that contains the total count of active data definitions. This information is used for DDA operations.
The PCR stores the basic parameters that define all configurable (and thus alterable) elements of the virtual supercomputer CPU. Such configurable elements include maximum field lengths, maximum register lengths, the number of registers in a stack, or the sizes of arrays and tables.
The Instantiation Unit (IU) creates the nodes and makes space for the nodes in the data representation. The IU contains one node index word (IW) in the node index word register (IWR). The IW contains a null flag that is set when a delete instruction is executed for a specified node. The next field contains the DDN. Following the DDN is a field that specifies the length of the data word. Next is the VNA, followed finally by an application-defined field (ADF). The ADF can be used for special purposes defined by the specific application.
The node-counter (NC) register is a virtual register containing a pointer to the next node. The NC contains a node number that is a non-negative integer specifying the relative address of the corresponding IW in the node index memory (NIM).
The Population Unit (PU) contains a node data word (DW) stored in a virtual register labeled the node data-word register (DWR-P). A DW may be fixed length or variable length. A fixed length flag indicates the type of a particular DW. The DW stored in the PU is used when populating the solution space (Node Data Memory, NDM) with nodes. The PU evaluates the data structure for a given node. The results of such evaluation are stored into a data word whose location in the NDM is pointed to by the index word. Every data word has a unique address in the NDM that is the VNA.
The navigation unit (NU), like the PU, contains a node data word (DW) stored in a virtual register labeled the node data word register (DWR-N). This value is used when navigating through the solution space.
The node index memory (NIM) contains the node free index (NFI) and the next free node registers (NFNR1 & 2). The NFI stores the current intervals of free nodes in the node index space. The NFNRs are loaded from the NFI, and store the beginning and the end of a range of free nodes. The primary use of the NFNRs is during instantiation operations where unused node index words are overwritten.
The arithmetic and logic unit (ALU) is a software implementation of some functions that are often implemented in hardware. It contains an adder/multiplier, a logic evaluator, an arithmetic register (AR) stack, a lookup table index, a function index, and an ALU memory. It allows as well for 'pass-though' of arithmetic operations to the underlying hardware CPU.
The physical memory controller (PMC) operates between the NIM and the NDM. The PMC controls the use of physical memory devices such as random access memory (RAM), disk drives, optical storage drives, and other physical memory devices which may be available to store data.
The network control unit (NCU) handles the low-level details of sending out data and processes to be processed. It in turn is controlled by a network manager. These two units handle the tasks of separating tasks to be run concurrently, load balancing, and other network and concurrency-related management tasks.
The CE store configuration parameters in the PCR, and also creates and stores data definition words (DDWs) in a manner depicted by the pseudocode in
The IE creates nodes in a manner depicted by the pseudocode in
The population engine (PE) evaluates and stores nodes in a manner depicted by the pseudocode in
The navigation engine (NE) finds and reads a node data word in a manner depicted by the pseudocode in
The evolution engine (EE) adds, deletes, or modifies nodes in a manner depicted by the pseudocode in
Further details regarding this invention are described below.
NVSI (Netcentric Virtual Supercomputing Infrastructure) is a technology that provides a software solution for a broad range of computationally demanding problems—in a myriad of commercial domains—that would normally require a dedicated supercomputer or large-scale, special-purpose, 'one-off' software. The core of NVSI is a system architecture that blends key ideas in computing, some rather novel, and some imported and modified from discrete mathematics, analog and digital computing theory, high-performance computing, and hardware supercomputers. The most unique aspect of NVSI is the design philosophy, derived from a biological perspective, in which analogs of evolution and growth provide computational structures and representations that are dynamic, flexible, adaptive, and work "well enough" under the constraints of imperfect and incomplete information.
As analogy, the human brain is not the ideal solution that a computer engineer would construct from scratch. The brain is, in effect, a hodge-podge of accumulated structures and algorithms that includes the biological equivalent of dead, buggy, bloated, contradictory, redundant, expensive, unstructured, inelegant, non-optimal and apparently useless code, and yet it solves an enormous range of changing situational problems. It doesn't always, or even usually, provide perfect results in an ideal sense, but the brain does yield workable and often novel moment-to-moment solutions that accomplish the task at hand.
Fundamentally, NVSI is a substrate that embeds biological notions in a system architecture, a virtual machine enabling construction of high-performance applications that provide superior solutions to certain classes of problems arising in a variety of industries. In particular, NVSI creates a common computing foundation that applies to widely disparate domains, where the shared theme is the rapid response to complex and fluid user demands not requiring the real-time analysis of a massive flood of streaming data, and for which the solutions may be imprecise and incomplete, but sufficiently accurate and robust to relieve the burden on brute-force processing, and to dramatically enhance the responsiveness of the system.
Some typical domains of application include:
financial risk-analysis & portfolio valuation
e-commerce procurement & catalog management
customer, vendor and peer-to-peer knowledge capture
telecommunications call-routing
high-demand query caching
customized global media distribution, and
fraud detection.
1. NVSI Features
The innovations of NVSI, beyond the leading one of creating a virtual supercomputer in software, include the merging of existing high-performance computing techniques and designs with the employment of novel approaches to computation, such as the separation of pre-computation from navigation to dramatically reduce real-time overhead, biologically-inspired "good enough" solutions, and the use of evolving data structures and adaptive computational architecture. In particular, key aspects of NVSI are:
NVSI is a virtual computer, composed of an operating system and a quasi-general-purpose, reconfigurable, multiprocessing, network-based, asynchronous RISC machine, that happens to be created in software only, and is designed to provide high performance over a large class of specific business-computing problems. NVSI can be implemented on a mosaic of platforms, and an increase in power of the underlying physical CPUs simply enhances the overall performance of the system.
One may ask: how can a layer of software be more powerful than writing code directly to the underlying physical platforms? The answer, of course, is that fundamentally, it can not. However, by acting, essentially, as an alternative computing architecture, NVSI is designed to expose to the system developer a landscape of primitive (that is, elementary) operations essential to the kinds of problems for which the features of NVSI are optimum. Thus, applications can be quickly developed for the relevant domains, without a business having to employ extensive labor resources to create a special-purpose, dedicated 'one-off' solution at enormous cost. Further, the internal NVSI operations use as few and the fastest platform-CPU instructions as possible, thus maximizing performance and avoiding the 'bloat' and wasted power inherent in general-purpose microprocessors. And last, NVSI bypasses the platform OS and makes direct calls to the platform CPU, thus eliminating one software layer that applications would typically be forced to use.
The result is that NVSI squeezes maximum performance out of the underlying CPUs, while providing to the developer a set of operations optimally suited to the problem at hand. With computational power proportional not only to speed and storage, but also to utility, and inversely proportional to capital and human resources consumed, NVSI outperforms both hardware supercomputers and custom vertical applications in power per dollar, when applied to the problems for which it is designed.
As in any computer, there are CPUs that include functional units, memory stores, and dedicated registers, all of which execute machine-instructions coded by system programmers. The core of the NVSI System is composed of the NVSI Virtual Machine (VM, the 'hardware') and the NVSI Operating System (OS). The NVSI-OS is an integrated collection of managers, engines and Toolbox macros, all written in an NVSI control language (NVCL), which is assembly-like and makes direct calls to the virtual hardware.
A typical system configuration for an NVSI installation is shown in
The units and their basic functions follow. For reference, the NVSI Register & Memory-Word Specifications are shown below, and the NVSI Machine Instruction Set is shown in Table 1 (both are discussed in more detail in later sections).
Solution-Space Configuration Unit (SCU)
Instantiation Unit (IU)
Population Unit (PU)
Node-Counter Register Unit (NC)
Navigation Unit (NU)
Index Memory (IM)
Data Memory (DM)
Arithmetic & Logic Unit (ALU)
Physical Memory Controller (PMC)
Network Control Unit (NCU)
Multiprocessing is built into the NVSI architecture on several levels:
The various engines are low-level modules in the NVSI-OS that generate the actual machine code sent to and executed by the Units of the VM. Thus, the Instantiation Engine, for example, runs procedures to create nodes, the Population Engine procedures fill (evaluate & store) nodes, and so forth. Calls to the engines are made from the OS managers (or perhaps the application directly) as tasks, such as "Instantiate 500 nodes", with associated parameters passed to the engines. Some typical engine procedures are shown in
The Toolbox is simply a collection of generic engine programs that have wide utility, both for low-level OS tasks, and application-level functions that are generic across domains. The Toolbox enlarges as experience with various application domains yields engine code that is used repeatedly.
Daemons are autonomous programs used for concurrent, dedicated processes that operate in the background to collect garbage, prune trees, condense redundancies, process edit-queues, etc.
Manager Descriptions
While the Engines implement various tasks, the NVSI-OS Managers coordinate among tasks. These include network, thread, data-distribution, & multiprocessing managers, as well as engine managers that handle the coordination of all the different tasks for a particular engine, in a higher-level manner accessible to the NVSI API.
3. Writing NVSI Programs with NVCL
NVSI Control Language (NVCL) is the assembly-level language composed of two coding schemes:
OS engine and/or manager programs are written in NVCL. In subsequent versions of NVSI, there may be provisions for each unit to maintain its own program counter, and thus its own flow-of-control.
A typical engine program in NVCL has the following structure:
EL code
VML code
{close oversize brace}
Embedding Language Control Structure
EL code
VML code
{close oversize brace}
EL structure
EL code
EL code
NVCL Examples
For all example code-fragments, the Embedding Language (EL) is a form of pseudo-code, in which boldface indicates a keyword, italic denotes a variable name, and underline indicates a named constant. For virtual-machine instructions (shown in monotype), operands appear in sequence after the operation, separated by spaces. 'True' values are coded as '1', 'False' as '0'. A 'null' value codes a non-operative variable or operand.
Virtual Machine: Register and Memory-Word Specifications
All word/register configurations are illustrated as follows:
The NC is the node-pointer. Its contents are the node-number NodeNum, an integer that is also the relative address (starting at zero) of the corresponding node Index Word (IW) in the Index Memory (IM). Thus,
0≦NodeNum≦Ω, Ω≡maximum number of nodes=maxNodeNum.
Index-Word (IW)
Index-Word (IW) lenIW = 1 [ +lenDDN] [+ lenLenDW] + lenVNA + lenDP (from DDW) # of fields = 2 + k (from DDW) + IBR(3) + (<FixLenFlag> = 0, from DDW for DW) # of fields = 1 + k (from DDW)
The IW typically functions as the index (index version) for an associated data word (DW), but the IW can be used as an indexed data-word itself (data version), for optimal performance where the data structures are fixed-length and simple.
An IW is always fixed-length, and all words in a memory segment are the same length. This allows for RAM-like storage and retrieval of index words. The address of each IW is its node-number (NodeNum).
The <Null Flag> is set only via a DEL instruction. It is redundant, as the null status of any node can be extracted from the Node-Free Index (NFI), but the flag provides faster access to null status at minimal storage penalty.
The optional <DDN> field specifies the data-definition number for the associated data word. It exits if the <DDN-D Flag> of the corresponding Index Base-address Register (IBR) is 1, indicating that the data-definition number is specified in the IW instead of by the <DDN-D> field of the IBR.
The optional <lenDW> field defines the length (in bytes) of the associated data-word (and DW register) for the index version of the IW. It exists if the data-word is variable length, as specified by a 0 value in the <FixLenFlag> field of the data-definition for the data word (available from the DDR register in the SCU). Otherwise, the length is specified in the DDW.
The composition of the Application-Defined Fields in the IW is contained in the corresponding Data-Definition Word (DDW), which is specified in the relevant IBR for the index-memory segment that includes the given IW (addressed by node-number). The DDW is selected by its Data-Definition Number (DDN), and the default DDW that specifies all index-words is DDN 1.
There are a fixed number of ADFs for both versions of the IW, and all fields are fixed-length. Thus, for a DDW that specifies the configuration of an index word, there is only one definition-packet (DefPak—see DDW word, below). Index-Word Register (IWR)
The IWR holds the contents of one index word, to be either stored into or read from the IW pointed to by NC. The <NodeNum> field is valid only after a read operation, and serves as a memory-address register to retain the last node-number accessed.
In 'compact' mode, the contents are loaded as one binary super-field (operand), either as read from memory, or as constructed from concatenating and encoding all component operands of the embedding-language variables into one bit-string. The parsing of the index-word after a read is done at the engine level, using the specifications contained in the corresponding DDW.
Data-Definition Word (DDW) & Register (DDR)
Data-Definition Word (DDW) & Register (DDR) DefPak: lenPak = 4 + len(max k) + FNF � {FLF � lenLenDfld � [1 + (k-1) � ASL′ ] + lenTNum � [1 + (k-1) � AST′]} + FNF′ � {FLF � ASL � lenLenDfld + lenTNum � AST}
A DDW specifies in detail the architecture of any data words, and/or the data-portion of the index words. The selector is the Data Definition Number <DDN>. The DDN is not a relative address into the array, it is merely an application-defined integer label (although it is unique). This allows for particular DDNs to be retained for corresponding DDWs, without the need for reassignment and/or word-swapping in the array. The actual addressing of array words is handled internally by the SCU.
When a DDN is specified (≧1) in a data-definition loaded into the DDR, and a store-data-definition instruction is executed, the internal controller checks to see if the DDN is new. If so, the DDW is written over a null array word (an unused, or available, memory word, indicated by DDN=0). If the specified DDN is not new, the existing DDW word with the same DDN is overwritten by the contents of the DDR.
The <FixLenFlag> specifies that the entire data-portion (DP) of the definition is fixed-length, and the length is then contained in the <lenDP> field. Although this information could be derived from real-time extraction of the relevant fields in the definition word, these two fields provide fast access for fixed-length configurations. If the DDW applies to an Index-Word (IW)—which are, by definition, fixed-length—then the <FixLenFlag> field is ignored.
If <FixLenFlag> is 0 (variable-length), then the length of each data-word is computed during instantiation or population, and stored in the <lenDW> field of its corresponding IW.
The details of the data-definition are contained in some number j (from the <NumDefPaks> field) of definition packet (DefPak) meta-fields, which are collections of field-specifications for each packet. If the DDW applies to an Index-Word, there is only one DefPak.
Each DefPak specifies whether or not there a fixed number of fields (<FNF>=1), and if so, the number (k) of fields is given by <NumFlds>. If all the fields in the packet are fixed-length (<FLF>=1), then the length is given by the <lenF-k> fields. And if all the fields are the same length (<ASL>=1), then the length is given by just the one <lenFld> field. If the number of fields in the packet is variable (<FNF>=0), then the field lengths are stored in each data-word. Note that if the global FixLenFlag=1, then all <FNF> and <FLF> fields are taken to be 1.
Similarly, the data-field types are given by the <TN-k> fields, where field type includes: tag, flag, character, integer, fixed-point, floating-point, function-pointer, node-pointer, and list-pointer (the table of data types is stored in the Field-Type Table in the SCU). And if all the fields are the same type (<AST>=1), then the type is given by just the one <TypeNum> field. The case where the number of fields is variable (<FNF>=0) and the fields are not all the same type, is not allowed, as this would force the storage of field types in the data word, which is a complexity not part of NVSI version 1.0.
Data-Word (DW)
Data-Word (DW) 1) FixLenFlag 1: 2) FNF 0, FLF 1, for some packet i (1 ≦ i ≦ j): 3) FNF 1, FLF 0 for some packet i: 4) FNF 0, FLF 0 for some packet i:
Data words come in one four basic configurations, depending on whether the data-definition specifies:
Note that in the latter three, the number of fields and/or the field-lengths must be stored in the actual data word. Note also that the condition where a variable number of fields in some part (packet) of the data-definition also does not have all fields of the same type, is forbidden in version 1.0 of NVSI, as it would require the storing of field types in the data-word as well. This level of complexity may be supported in subsequent versions.
Data-Word Registers (DWR-P & N)
The Data-Word registers (one in the PU and one in the NU) hold the contents of one data-word, to be stored into (DWR-P) or read from (DWR-N) a data-word in the DM (at the VNA specified in the associated IW). In 'compact' mode, the contents are loaded as one binary super-field (operand), either as read from memory, or as constructed from concatenating and encoding all component operands of the embedding-language variables into one bit-string. The parsing of the data-word after a read is done at the engine level, using the specifications contained in the corresponding DDW. The length of the register is specified either by the DDW (if the fdata-word is fixed-length), or the associated IW (if variable length).
Number of Nodes Register (NNR)
The NNR holds the current total count (=NumNodes) of non-null nodes. This is used for iterating node-creation and population operations, and also for display by the NVSI Console Monitor.
Data-Definition Count Register (DDCR)
The DDCR holds the total count (=NumDD) of active data-definitions. This is used for DDA operations, and by the NVSI Console Monitor.
Node Free Index (NFI)
The NFI stores the current intervals (inclusive range) of free (available, or 'null') nodes in the node Index Memory. Although a one-bit boundary flag is strictly sufficient to distinguish between a single node entry (for isolated free nodes), and an interval that requires two node-numbers to specify, a two-bit flag is used to provide for error-recovery in the event of a system crash, so that the NFI can be reconstructed. The <boundary flag> indicates one of three conditions that apply to the subsequent <NodeNum> field: single-node, node-interval-start, or node-interval-end. Thus, for example, the following would specify that the next free nodes are 17, and then 23-28: . . . 11 17 01 23 10 28 . . . ,
NFNR1 & 2 are loaded—via the Get-Free-Node-Range instruction—from the Node-Free Index (NFI). Their primary use is for garbage collection, and for subsequent instantiation operations, to allow overwriting of unused Index words. The GFNR instruction is the only operation in the VM that invokes a significant sequence of embedded microcode, which searches the NFI for the first node-number greater than or equal to the value of the NC, and then loads the NFNR1 with that number, and NFNR2 with the end number of the range.
Field-Type Register (FTR) and Table (FTT)
The FTT is a firmware table in the SCU that stores the list of preset data-word field types (tag, flag, character, integer, fixed-point, floating-point, function-pointer, node-pointer, and list-pointer). The FTR is a register in the SCU that is used to hold FTT words for storage or retrieval.
The FTT is extendible via SCU instructions from the Configuration Engine.
Index-segment Base-address Registers (IBR) and Stack
To provide for the segmenting of the solution-space into portions that share identical index and/or data-word configurations, but are distinct from other portions, the VM supports a simple indexed-addressing mechanism. Each IBR stores a base index address (node-number) that delineates the lower boundary of an index-memory segment that has common index-word definitions. Thus, any node whose address is greater than or equal to <NodeNum>, and is less than the node-number field of the next IBR, has the same configuration. The configuration of all the index words in the segment is given by the DDW pointed to by <DDN-I>.
The IBR stack consists of a set of NumIBR index base registers. If, at any point in the stack, the next IBR has a null <NodeNum> field, then the upper bound of the previous segment is taken to be maxNodeNum (that is, the end of Index Memory).
The <I/D Flag> determines whether (1) or not (0) the index words in that segment serve also as data-words. If so, then the subsequent fields in the IBR are ignored. If not, then all of the data words may share the same configuration (<DDN-D Flag>=0), which is then described by the DDW pointed to by <DDN-D>. This allows for matching homogeneous index and data segments. Otherwise (<DDN-D Flag>=1), the data-definition pointer for each data-word is stored in its respective index word (in the <DDN> field).
The IBR stack is loaded via the set-index-base-register instruction to the SCU.
Arithmetic Stack Register (AR)<
Parameter Configuration Register (PCR)
The PCR stores the basic parameters that specify all the configurable architectural elements of the VM. These include the operating modes, field and register lengths (bit widths) for various components, and the number of registers or memory-words in the various configurable stacks, tables, and arrays.
Virtual Machine Language (VML) Instruction Set
set NC
Set NC to <opnd.NCl>.
Increment NC by one or <opnd.NC2>.
Decrement NC by one or <opnd.NC2>.
load PCR
opnd. CU1
Set each field in the PCR to its
corresponding element in the integer-
array <opnd.CU1>. The dimension n of
CU1 is the number of fields in the PCR,
given by
<opnd.CU1 (0) >→ PCR(0) ≡ NumPCRflds.
Set the IMA register to the amount of
(set) IM
memory, in megabytes, to be allocated
to index-memory, as given by
<opnd.CU2 (0) >, and set the DMA
register to the amount of memory
allocation for data-memory, as given by
<opnd.CU2 (1) >.
load DDR
Set each field in the DDR to its
corresponding element in the variant-
array <opnd.CU3>. The dimension n of
CU3 is available from the configuration
details of the data definition. If n =1
(one element), then the single operand
field is loaded into DDR(0) to specify the
DDN for a subsequent read (GDDW)
store DDA
Store (write to) each field in the DDA
memory- word pointed to by DDN =
DDR(0) with its corresponding field
value in the DDR. If the DDN is new
(not found in the DDA), then increment
DDCR. If <opnd.CU4> = True, then the
instruction becomes a delete, and the
DDN of the correponding DDA word is
set to zero (which flags the word as
null), and the DDCR is then
Set each field in the DDR to the
corresponding field in the DDA word
DDA word
pointed to by DDN = DDR(0).
clear DDA
Set the DDN field of all DDA words
(count given by DDCR) to zero. Set
DDCR to zero. This happens by default
at "power-up" (initialization).
Load the FTR from <opnd.CU5>, then
execute a store into FTT word pointed
Type word
to by FTR(0) = CU5 (0) ≡ TypeNum. If
<opnd.CU5> is a single element, then
only FTR(0) is loaded, and no store is
executed, in preparation for a
subsequent read (GFT) instruction.
Load the FTR from the FFT word
(read) FT
pointed to by FTD(0) ≡ TypeNum.
set an IB
Set all fields of IBR(i), where i =
<opnd.CU6>, to <opnd.CU7>.
read IW
Set IWR to IW(NC). This allows the
reading of IW contents, primarily as a
precursor to navigating, populating or
re-instantiating a node.
load IWR
If the VM is operating in 'compact
mode', then the single (n = 1) operand
bit-string is loaded into the IWR (Index
Word portion).
Otherwise, the fields of the IWR, as
defined (prior) by the configuration of
the DDW pointed to by the DDN-I field
of the relevant IBR (based upon NC), are
loaded from the corresponding
operand-array elements. The length of
the IWR, and the number of fields (the
dimension n of the operand array), are
calculated prior to this associated DDW.
This instruction is typically a
precursor to executing a CRE instruction.
If <opnd.I2> = True, then create
(instantiate) a node at node-number =
NNR, else create node at node-number =
NC (default). To create a node, the
contents of the IWR (except the Null
Flag), are stored as an IW in Index
Memory at relative address = node-
In 'compact mode', this is a simple
binary transfer. Otherwise, the fields of
the IWR are stored into corresponding
IW-array elements.
The NC is then incremented (to
optimize serial instantiation).
If the node had been null, then clear
the Null Flag of the IW is a data version,
then the ADFs may be null, to be filled
later via a PDW instruction.
Delete node (set Null Flag) in IW at
node-number = NC.
Also, if node had not been bull, then
update NFI, and decrement NNR.
get free
Sets NFNR1 & NFNR2 to the boundaries
of the nect-free-node-range, where
NFNR1 ≧ NC. (The internal IM
controller scans the NFI, and finds the
first null node or node-range ≧ NC. This
instruction is therefore slower, as it
executes an embedded microcode
load DWR
If the VM is operating in 'compact mode',
then the single (n = 1) operand bit-
string is loaded into DWR-P.
Otherwise, the fields of DWR-P, as
defined (prior) by the configuration of
the DDW pointed to by either the DDN-D
field of the relevant IBR (based upon
NC), or by the DDN of the associated IW,
are loaded from the corresponding
operand-array elements. The length of
the DWR, and the number of fields (the
dimension n of the operand array), are
calculated prior to this instruction, from
details contained in the associated DDW.
If <opnd.P2> = True, the IW is a data-
version and the contents of DWR-P are
stored into the data portion of the IW
located at address = NC.
Otherwise (index version), store the
contents of DWR-P into the DW located
if <opnd.P3> = False (pre-execution
address retrieval), then VNA ← IWR(VNA);
else (execution-time address retrieval),
Note that if the length of the DW has
changed, then a new VNA must be
obtained by the DM internal controller
(in conjunction with the PMC), which
then automatically rewrites the new VNA
into the corresponding field of both the
IW, and the IWR
In 'compact mode', the store operation
is a simple binary transfer. Otherwise,
the fields of the DWR are stored into
corresponding DW (or IW) array
The NC is then incremented (to
optimize serial population).
Load DWR-N with the contents of the
(read) DW
DW at the VNA selected by <opnd.N1>,
same action as for <opnd.P3>.
GDW is the basic navigation operation.
[ ] optional operand
< > operand name in text
≡ 'is defined as'
The following description advances and details the concept of implementing a novel software architecture on a heterogeneous network of conventional computational platforms to create a Netcentric Virtual Supercomputer Infrastructure (NVSI). In order to provide a full appreciation for the commercial importance of this breakthrough enabling technology, the description also describes one possible application of the NVSI, named RiskScape. The RiskScape application addresses a particular computationally-intensive problem in financial risk management known as Portfolio Stress-Testing.
We begin by discussing why this technology represents a breakthrough, and we then enumerate the several innovations that we have brought to bear in order to achieve this breakthrough. We next discuss the nature of how NVSI accomplishes its radical level of performance without special-purpose hardware. We then review the reasons why we believe no one has heretofore taken this approach to computer system design.
The description continues with a mathematical treatment of the RiskScape design in order to demonstrate the power of the NVSI technology. In this section we outline the assumptions we have made to make the problem computationally tractable, as well as discuss several of the optimization techniques that the NVSI platform provides to the application developer.
Finally we make a comparison of the NVSI technology with hardware-based supercomputers. This comparison addresses both the classes of problems to which NVSI is suited, as well as a discussion of those to which it is not. The last comparison is in price/performance. Here we show the estimated computational throughput of the NVSI system in terms of VFLOPS (Virtual Floating-point Operations per Second), and compare this with two CRAY RESEARCH machines, the T90 and the T3E.
Our findings conclude that for certain classes of problems for which pre-computation is a viable methodology, the NVSURiskScape solution is capable of about 250 (Virtual) GigaFLOPS. This performance is comparable to that of the CRAY T3E. Most importantly from a commercial perspective, we estimate that the cost of an NVSURiskScape implementation will be on the order of 50 to 100 times less than a comparable hardware-based solution.
Netcentric computing is the new paradigm for building efficient, cost effective computer systems to solve numerous business problems. Many commercial enterprises have invested substantial sums in computer hardware only to discover that they realize a fraction of the total CPU power. This is because the operating costs of a piece of hardware are identical whether the machine is running at its peak capacity, or sitting idle. The problem is compounded by the fact that while one machine is sitting idle, another in the same office is so overloaded that it has slowed to a crawl. What is needed is a way to allow the power of idle, or underutilized, machines to automatically augment the capacity of those that are over burdened. Such a solution would allow businesses to add hardware in an incremental fashion, rather than having to continuously upgrade expensive servers and mainframes.
This description describes a breakthrough, software-based enabling technology that transforms a network of conventional PCs, workstations and servers into a virtual supercomputer designed for optimal performance over a wide class of commercial domains. Quite general in nature, this virtual supercomputer can be used to solve many (although certainly not all) computationally intensive problems that are found in a number of different businesses. These include telecommunications switching, investment-portfolio valuation, e*commerce order processing, high-demand query caching, and fraud detection, to name a few.
So that our proposed technology does not begin life as a solution in search of a problem, we have applied virtual supercomputing to the problem of Financial Risk Management. Specifically, we have Portfolio Stress-Testing an area that has a significant need for a cost-effective solution, and for which our new technology is well suited.
However, it must be appreciated from the outset that while we describe a specific application, this should in no way imply that the underlying technology is limited to this application. Our sole purpose in blending the description of the risk management application with the enabling technology in this paper is to demonstrate the vast cost/performance benefit.
RiskScape: An Application of Netcentric Supercomputing to a Business Problem
It is clear that many commercial problems, such as Financial Risk Management, need the level of computational power associated with conventional hardware-based supercomputers. Unfortunately, unlike mission-critical projects for military and government operations, the commercial world is highly constrained by economic considerations. In the main, businesses cannot justify the expenditure of tens, if not hundreds, of millions of dollars on computer hardware that will become obsolete in three to five years. This is true even though rapid and accurate risk management can spell the difference between business success and catastrophic failure.
What is needed for commerce is a viable solution that transforms the substantial hardware investment already made by a firm into a computational platform capable of supporting the necessary time-critical decision process. In this description, we outline our design for such a computer system (termed Netcentric Virtual Supercomputer Infrastructure or NVSI), and then continue to describe one commercial application (RiskScape) that together can provide the level of performance financial institutions require in order to manage their risk.
Our current best estimate of the sustained "Virtual FLoating-point OPerations per Second" (VFLOPS) obtainable by our risk-management application supported by our proposed NVSI technology, is between 5 and 250 GigaFLOP (billion floating-point operations per second), depending on the number of CPUs available to the system. This meets the computational power of a CRAY RESEARCH T3E, the highest-end commercially available supercomputer.
This translates as the ability to evaluate a portfolio consisting of one million instruments (including portfolios of derivatives on both debt and equity instruments) across three million scenarios in under one hour.
It is important to note that the solution we propose is software based, and requires only an incremental amount of additional hardware. From an economic and commercial standpoint we estimate that a full NVSI/RiskScape implementation will be between 5 and 10 million dollars. A hardware-based solution with comparable performance would cost in excess of 50 to 100 million. Moreover, unlike a hardware solution, the NVSI system will not become obsolete with advances in computer technology. Indeed, performance only improves with evolution in platform and network capability.
Computing portfolio risk (PR) is a problem taking center stage in investment risk management. Managing risk is not trivial. Banks and other financial institutions are in the business of taking risks to generate increased revenues and profits, but they are also required to protect shareholder value and prevent catastrophic losses from occurring. To date, evaluation of PR has mostly been confined to macroscopic aggregate measures such as Value-at-Risk (VaR), which estimates PR as an expected loss derived from a weighted sum of volatilities in the individual securities in the portfolio, based on small, statistically-derived market moves. Current risk management systems thus do an effective job of characterizing the expected loss in linear portfolios operating in normal markets. Indeed, some form of full Monte Carlo VaR is the state-of-the-art for both market and credit risk measurement.
Yet, VaR indicates only the maximum expected loss that could occur over some time interval (the portfolio holding period) within some confidence level (usually 2σ or standard deviations, about 97.5%). VaR has nothing to say about discontinuous or extreme (3σ+) market events, such as the Russian Sovereign Debt, and Japanese and Emerging Market currency crises. That is, VaR ignores the "fat tails" in the distribution of portfolio values within which lurk the "dragons" of risk, the unexpected large moves in financial variables that can cause substantial losses, as have been suffered by a number of leading financial institutions over the last several years (such as LTCM). And given that the financial markets are not normally distributed (they are log-normal), such events happen with considerable—and distressing—regularity. To cover the possibility of extreme events, financial institutions implement large safety factors, as the absence of specific risk data for the "tails" induces great caution. The result is that excess capital is lying dormant, an inefficient solution at best. Moreover, if the VaR method is pushed to achieve a greater range of application, severe computational limitations arise. Finally, even setting this consideration aside, VaR calculations still do not really address the "What if?" scenario questions.
In light of these limitations, the method of stress-testing has evolved as a complement to VaR. Also known as scenario analysis, this approach attempts to address the weaknesses in VaR by subjectively generating scenarios that simulate large-variance events. This enables the handling of nonlinear positions, and certainly fills in some of the gaps. But, current implementations of stress-testing are flawed because of the small number of scenarios that can be examined (due to computational constraints), thus forcing necessarily subjective choices about which extreme changes to evaluate. The method also considers movements in only one, or few variables, and correlations are virtually ignored. And most glaring of all the defects in current stress-analysis of PR is the inability to forecast path-dependent scenarios several time-steps into the future, again due to limits on computational resources.
Even if the appropriate predictive tools existed (such as comprehensive scenario-analysis systems that accessed rich historical data combined with "mark-to-future" states), the sheer data problem is enormous. Further, the integrity of the data is crucial for assuring the validity and integrity of the risk management process results. Real issues of analytical model fidelity and accuracy compound these challenges. New financial products are finding their way to market (credit derivatives, synthetic financial products, etc.) at an accelerating pace. As the worlds of market risk and credit risk begin to merge, there is an accelerating pace in transaction volume growth. It is increasingly clear that the standard approaches to managing risk are not keeping pace with the problem domain. The approach to problem solving in the risk management marketplace today is gated by problems of computing power; database transaction processing throughput, application design, application scalability, and user interface technology.
Of course, this is not news. It is well known that the ideal approach would be to simulate the detailed price trajectory for all the instruments in a portfolio, over a broad range of path-dependent scenarios, using the best (perhaps several) pricing models available (or Monte Carlo simulation, finite-difference methods, numerical integration, or tree expansion, where closed-form models do not exist), all calibrated by accumulations of historical data to provide correlation coefficients, scaling factors, and transition-probabilities for variations in financial parameters. The difficulty has been that such an approach requires an enormous amount of computing power (on the order of leading-edge supercomputers), at a cost that is daunting to even the most resource-rich investment banks. So, we settle for VaR, and a lot of theoretical modeling and projection. But, risk analysis must be essentially data-driven, not a theory-driven exercise performed in a data vacuum.
This description outlines a new technology that allows, for the first time, a practical solution to the problem of calculating future risk for large-scale portfolios. We present a novel computing architecture—essentially a software-based "virtual supercomputer"—that supports on-demand access to projected prices over portfolios of O(1M) securities, for a full range of path-dependent scenarios that entail large (3σ+) moves in financial variables. Termed NVSI (Netcentric Virtual Supercomputer Infrastructure), the system is a suite of highly-optimized system kernels and user applications, designed to emulate the key aspects of supercomputer architecture (tools, techniques, and algorithms), running on off-the-shelf workstation and network hardware, for about 1/100th the overall cost of a dedicated supercomputing system.
How does it work? In brief, by continuous off-line (background) computing, the RiskScape/NVSI constructs a daily updated landscape of projected portfolio values for a broad range of scenarios, along with associated scenario probabilities. This multidimensional state-space (hyperspace) can then be queried to yield near-real-time answers to questions such as: which scenarios (if any) could result in catastrophic loss to my portfolio in a week, ninety days, and six months out, and with what likelihood?
By using supercomputing techniques emulated in software, model optimization, massive non-swappable RAM, and distributed processing over commercial networks of existing workstations, the NVSI first populates a hyperspace of up to 10 billion nodes with state-vectors that contain the pricing information (and other moments) for the entire range of instruments in a portfolio of up to 10 million securities. Once the hyperspace is fully populated with pricing vectors, the portfolio can then be marked to any future state (scenario) desired, simply by looking up (or navigating to) the address of that state and applying the pricing vectors to each instrument. The computational overhead of this second phase is minimal, as the vectors have been pre-computed off-line. Clearly, the combinatoric nature of the problem requires that the solution space be properly constrained. To do this correctly, the optimal granularity and distribution of the state-vectors in the hyperspace must be determined to ensure that the problem domain is fully bracketed.
If the set of state-vectors is chosen appropriately, the entire landscape of scenarios can be searched for the extreme events. In fact, the application can be programmed to find the boundary conditions for catastrophic loss. In other words, the NVSI system can actively search future state-space to determine what combination of market and/or credit conditions would cause the portfolio (or institution) to fail. In addition, the probability of these conditions obtaining, and the likely amount of time required for the conditions to obtain as well as the transition states through which the world must pass to reach the final state, can be determined.
Such information would allow strategic management to see problematic conditions in advance, and take appropriate action. Problematic financial and non-financial holdings can be analyzed, understood and unwound before potential financial meltdowns occur.
Why hasn't this been done before? The answer is, because the computing demand is enormous, the price/performance ratio for available technology has just recently come within practical range, and no one has heretofore applied a blend of software solutions using virtual-supercomputer architecture, off-the-shelf network hardware, background computing, a spectrum of numerical optimization techniques, and domain-specific "tricks" to make the computational problems more tractable.
Large-scale computing problems have been around since the Manhattan Project, and indeed, Los Alamos was the necessity that mothered the invention of DBM (colloquially named "Dah Big Machine"). Until recently, development of DBMs, now known as supercomputers, has been driven by military and civilian government needs, and hence, contracts. Typical application domains have been weather forecasting, code breaking, signal and image processing, intelligence evaluation, aerospace engineering, and nuclear weapons design. The resulting machines were designed and built with cost as no object, and their prices reflect that history. Spending $50M-$150M on a dedicated number-cruncher is an expense difficult to justify for an investment bank, especially when that glistening rocket ship will become a burdensome dinosaur in about three years.
The alternative has been to scale-up existing software that calculates trajectories for individual instruments, such as options and other derivatives, using pricing models like Black-Scholes. These programs work perfectly well, and provide a flexible platform for future improvements, except that they provide single-instrument answers for one input vector in time-frames on the order of a minute, or at best, several seconds. This is fine for the trader negotiating a position, but when this performance is expanded to include a family of trajectories arising from a wide range of scenarios, and then further multiplied by up to a million instruments in a large global portfolio, even brave souls pale. Waiting a hundred days or more to get an answer somewhat moots the requirement for daily update and response.
The application of the NVSI techniques, in coordination with the recent convergence of several other factors, enables the construction of an affordable virtual-supercomputing system that can usefully meet the need for large-scale, near-real-time portfolio risk analysis. These recent factors are:
In essence, no one has demonstrated a software-emulated supercomputer, because the performance would be too slow for the real-time government applications listed above, and providing a one-off solution for near-real-time commercial needs would require massive construction of custom software at a cost nearly as burdensome as buying a big machine.
Instead, we have determined that it is possible to build a suite of leading-edge system programs and software applications, running on networks of off-the-shelf workstations, that gives dedicated, near-supercomputer performance without requiring much (or eventually, any) specialized hardware. Such an approach can evolve with improvements in hardware and software technology. When presented as a retail solution to potential client financial institutions at a reasonable cost ( 1/100th that of a dedicated supercomputer), the NVSI system becomes a viable product.
What is new here? What is not new is netcentric computing of large-scale problems. This has also been termed "Metacomputing" by the NCSA (National Center for Supercomputing Applications) and its affiliated institutions, and is being actively pursued as an alternative to single-box supercomputing, using wide-area networks of high-end mainframes. The innovation is in building integrated, highly-optimized software that emulates the kit of hardware supercomputing tools and techniques, to create a hardware-independent "virtual supercomputer", optimized to solve a wide class of problems that require large-scale evaluation of independent state-functions in an unbounded hyperspace of multidimensional inputs and outputs. Indeed, our architecture could be used to solve a range of similar problems in other domains, such as credit risk, query-caching, and transaction-processing for global compliance management on the interne, which are decomposable into separate processes of background pre-computation and real-time (demand-query) navigation of a large state-space. NVSI would not be suitable for a domain that required the system to "keep up" with a data stream from the "world" arriving in real-time, such as cryptographic analysis.
The following innovations and/or breakthroughs in RiskScape/NVSI are detailed in subsequent sections.
Innovations in Computational Design:
The functional block-diagram of the NVSI (
Data Structures
For each entity in the collection (each instrument-type in a portfolio, for risk applications), the NVSI constructs a path-dependent tree (a rooted, ordered, unidirected graph), also more generally termed a metastructure or scenario-tree. The branches (edges) represent variations ΔIx in input-parameter Ix with fanout κ. Every node (vertex) is a state-vector s containing the value (output) of one or more model vectors V for the given instrument (allowing for multiple models to value the same instrument), and the probability P(s) associated with that node (derived from the conditional probability of the particular input parameter variation that led to the current state), for each timestep tk in a sequence of chosen intervals. An example tree, for fanout κ=9, is shown in
For each node i (a point in the state space, H) there is an associated state s1, defined by a 7-tuple state-vector:
s i ≡<j,k,z,P(s i),n,V,V′>,
For RiskScape applications, the conditional probabilities are just the transition probabilities for changes in financial variables. In general, although the states (output function values) are not usually path-dependent (except for some exotic instruments), the transition probabilities are conditional. Thus, the probability of a change in volatility σ, for example, is dependent on the baseline:
P(s i |′s i)=P(Δσ|σ);
A particular state is defined by computing scalar values for all the variables (or functions) v defined in the state-vector, for the particular node in the tree.
Note that κ is just the total number of variations over I. The way that κ is mapped onto I, i.e., how the available granularity in variations is distributed across the input variables, is defined by the client-user.
Three key features of the data structure are:
This enables fast calculation of pointers, saves an enormous amount of storage, and wastes virtually no memory space. And because the trees are fixed until the state-space is recreated for a new domain and a new set of scenarios, there is very little shuffling or garbage collection required.
The total number of nodes (or states), Ω, in the hyperspace H is constrained by the total amount (in bytes) of dedicated MassRAM (denoted by Mem) available, and Λ, the characteristic length (in bytes) of the data words. Thus, Ω(H)=total number of nodes (states) in the hyperspace
As shown later, a typical instantiation for RiskScape yields Ω˜109 states.
A scenario is the path of events, or conditional changes, that leads to a given state. Thus, each node represents the result of one scenario. The entire set of scenarios yields a scenario-tree, which is exactly one metastructure. Note that, typically, different metastructures are defined on the same landscape of events, and thus share the same set of scenarios. The total number of separate trees is therefore constrained by both Ω(H) and the chosen fanout κ (derived from the desired granularity in input variation) and τ (the total number of time-steps desired in the analysis).
For balanced trees, the number of nodes M in a tree is given by the sum of a geometric progression of base κ:
The total number of available scenario-trees (metastructures), N, is therefore:
RiskScape Structures & Design Factors
The NVSI, along with the RiskScape Intelligent Financial Risk Application, was originally designed to optimize the computation of future portfolio values over a range of scenarios designed to uncover "dragons", the potential catastrophes that can result from less likely events (changes in relevant financial variables) that lie in the "fat tail" of quasi-lognormal (kurtotic) distributions presumed to underlie most financial variations. Typically, large global portfolios are composed of 100,000 to 10M instruments (securities), and include a wide range of types: stocks (equities), bonds, futures, currencies, swaps, convertible debt, interest-rate instruments, options (on all of these), and other exotics. Various models of these instruments exist, and the output variables include price and the various moments (the "greeks") of the model function. Typical input variables, which are changed systematically in a simulation to construct a scenario tree, include pu (price of the underlying asset), the asset volatility σ, interest rate ir, and interest-rate volatility σi
Probability Values
In the prototype version designed for use in financial risk analysis, the data structure has elements that are key for future-risk computation. For portfolio evaluation, the conditional probabilities P (ΔIx|Ix) correspond to the actuarial transition-probabilities derived from tables of historically-calibrated movements in financial variables, or extracted from relevant time-series of changes in those variables. For risk analysis, the risk-adjusted probabilities are also important, so the RiskScape interface allows the user to choose either, or both. If both are specified, one of the alternative probabilities is stored in one of the n variables v.
With a κ (fanout) of only 12-16, and four input variables, for example, there is not enough granularity to allow for joint transitions (such as Δσ=4 & Δpu=−0.5). Thus, in the prototype, branches typically denote orthogonal moves, that is, changes in one input variable at a time. However, implicit nonorthogonality can be approximated by using historically-derived correlations between financial variables. This approach relies on the fact that, with large moves, correlations between financial variables become tighter. Alternatively, κ can be increased to allow for joint transitions, consonant with available resources.
To make the computation tractable for large portfolios (1M+ instruments), and congruent with the theme of future-risk analysis, which is to look at possible catastrophes ("dragons") arising from large moves in the input variables, only changes of ΔIx> 3σ are typically evaluated. Although available tables of transition probabilities do not always contain such data, the required probabilities can be easily extrapolated, as the distributions (or at least the first moments) are known.
Instrument Proxies
Even with 128 GB RAM and modest tree size (κ=12 and τ=6), for large heterogeneous portfolios an unaugmented NVSI can support no more than ˜100-1000 metastructures (separate scenario trees), depending on the word length Λ. To compensate, one of the innovations in the architecture is therefore to use "virtual" or proxy instruments: state-vectors with V composed of generic model functions for all the securities based upon the same underlying asset (or base index). The actual instrument prices can then be calculated during navigation, by evaluating the corresponding function and converting back using standard scaling and correlation coefficients. When a proxy state is computed (during the hyperspace-population phase), the various prices and moments of a given model are calculated over a range of values, thus creating a parametric space that brackets the range of possible magnitudes for the portfolio instruments. During the navigation phase, the actual instrument prices (and other moments) are then calculated via extraction of values from the pre-computed parametric-space, using the state-dependent input parameters stored in the proxy state-vector.
For example, suppose the actual instrument is a standard European option, defined by free parameters K (=strike-price), S (=pu), r(=ir), (=div yield), T (=time-to-expiration), and σ(=volatility). If the model of choice is Black-Scholes, the option price can be obtained from a "normalized" space defined by only three parameters: {K/S, (r−δ)T, σ√T}. During the population phase, the parametric pricing space is pre-computed (creating a "parametric-hypercube") and mapped to the proxy, and the values of the input vector I are stored in s for each node in the scenario tree. Then, during navigation, the price p of the actual portfolio option instrument is calculated (marked to scenario) simply by extracting a virtual price pproxy from the associated parametric-hypercube using the input values (K, S, r, δ, T, σ) and then transforming the result using known scaling (α) and correlation (β) factors. That is,
p=p proxy�α�β
Recall that each different proxy represents instruments with different underlying assets, and each proxy is evaluated over one scenario-tree. Thus, the number N of available metastructures determines the number of available proxies onto which the portfolio can be mapped.
There can be many different classes, or types, of instruments in a portfolio, including:
1. Equities & their derivatives (d)
2. Debt Instruments & d
3. Swaps & d
4. Currencies & d
5. Collateralized Mortgage-Backed Obligations & d
6. Exotics (such as Interest Rate, Barrier, Lookback and Knockout options).
Some types are much more cumbersome to compute, as indicated above. For example, some of the exotics require complex use of input parameters, such as interest-rate derivatives that use a path-dependent interest-rate curve (or actually, an interest-rate vector). Models such as Heath-Jarrow-Morton and Black-Derman-Toy are valued with state-dependent trees, which the NVSI architecture already supports.
The proxy state-vector must contain models or parametric references for as many types of instruments as there are in the portfolio. For example, a proxy might contain variables for cash, futures, standard options (all Type 1), sovereign debt (Type 2), and interest-rate options (Type 6). All instruments of Type 1, 2, & 6 in the portfolio that are also based upon the same underlying asset or base index (such as the S&P 500), are linked to this proxy. Thus, there need to be as many proxies as there are underlying indexes in the portfolio (typically in the hundreds).
Data Word Structure
The structure and size of a data word (the bit-wise representation of a state-vector) is specified by the Data-word Definition Table (see MetaTables), which is constructed by the Instantiation Manager according to specifications received from the client-user. For each proxy, the Population and Navigation Managers carry this table around, so to speak, as a part of their operation.
Data-word structure is flexible. The default is as follows:
The back-pointer, j, indexes the branch (of κ) from the parent node that a state occupies. The prototype allows for a maximum fanout of κ=64, so the length of j in bits is:
len j=6 bits.
The prototype allows for up to τ=16 time steps, so
len k=4 bits.
The flag-vector, z, is one byte (to handle up to 8 conditions):
len z=8 bits.
Probabilities must reflect likelihoods derived from large-move events, and need be no more accurate than 1 part in 1000 (three significant digits). Thus,
len P(s)=10 bits.
The number n of variables in the value-vector V is unbounded, but the prototype allows for 256. Thus,
len n=8 bits.
Strictly, n is redundant, because the data-word-definition table (created by the Instantiation Manager) specifies the number of variables in the state-vector. Yet, placing n in the state-vector promotes data integrity, and its storage penalty is small.
The first part of a state-vector (everything but V), denoted by <s, thus has a length:
len <s=36 bits.
Finally, the variables in V can represent function outputs, parameter ratios, input variables, statistical-distribution points, partial-derivative values, or parameter-reference pointers. In general, the magnitude ranges are known and specified in the data-word-definition. Thus, the only part stored in the state-vector is the integer mantissa, again typically to three significant digits for dragon-hunting. In those cases where the range is arbitrary, or infinite, an integer exponent to accommodate 10�15(5 bits) is also stored. The default, then, is:
len v=10 bits or 15 bits.
For the complex proxy described above, which we shall use as a conservative benchmark, the state-vector would contain one function variable for a cash index, one variable for each of several (say four) futures, four variables from the input vector I=[pu, σ, ir, σi
There is also one variable required to store the alternate probability measure. Then,
n≡number of variables≅1+4+4+4+8+10 (or 5�2)+1=32.
If most of the price-related variables (cash, futures, curve-segments) require stored exponents, then
len V≅(15�15)+(17�10)=395 bits.
Accounting for the length of V′ (the time-dual of V), this yields
len s=len <s+2�len V=36+2�395=826 bits.
The actual word-length, in bytes, for our benchmark proxy state-vector, is then
Λ=┌len s/8┘=104 bytes.
This will be used to calculate relevant performance parameters.
Meta Tables
The user specifies the nature of the problem domain, and all relevant data, via the RiskScape Interface, using a Scenario Description Language (SDL). The Instantiation Manager then creates and configures a set of tables to implement the specifications. Typical tables include:
Some of the tables are quite large, such as the Portfolio Data (1 million records or more) and the Node Index (a billion records). All are stored on hard disk, but some are also resident in CPU RAM (not MassRAM, which holds only the hyperspace II), such as the Data-word Definition, Proxy Definition, Probability Transition, Input Variable and Scenario Definition tables.
The Infrastructural-Technology Suite
The core NVSI modules are:
In this section, boundary conditions and typical mid-range values for spatial (storage) requirements and temporal performance are derived.
Spatial Parameters
Recall that:
Λ≡characteristic data-word length, and
Ω(H)=number of available states in H≡Mem/Λ, Mem=available memory (in bytes).
Thus, for the prototype MassRAM of size 128 GB (=137�109 bytes), and a typical Λ (for our benchmark proxy) of 104 bytes:
Ω=(137�109/104)≅109=1 billion nodes (or states) available in the hyperspace.
Note that with a Λ˜50 bytes (for very simple Type 1-only proxies) to 200 bytes (for very complex proxies representing instrument Types 2, 5, & 6), the result is still about the same.
For the same size scenario tree as used earlier, with κ=12 (allowing three gradations, or moves, for each of four input variable) and τ=6 (allowing for six time-steps, such as 1 day, 3 days, 1 week, tVaR˜20 days, 3 months, 6 months), then
M=tree size≅126≅3�106=3 million nodes in the scenario tree.
N=number of scenario-trees=Ω/M=109/(3�106)≅300=number of proxies allowed.
The number of proxies available to map the portfolio onto is therefore about 300, for κ=12 and τ=6. Can a large global portfolio be mapped to only 300 proxies, that is, only 300 base indexes? Absolutely. There are only six types of proxies, and linking these to 300 underlying assets/indexes would cover most of the developed world.
To bound this result, consider a scenario tree with a larger κ of 16:
Since many portfolios require less than 100 base indexes, then with a typical N of ˜300 available for our benchmark tree of κ=12 and τ=6, the effective fanout κ can be increased (thus increasing the input-variation granularity), by indexing an array of proxies to one instrument-class, each identical except that the scenario-trees use different ΔI increments. For example, one tree could assign each branch to variations of (0, �3σ), another tree have branches for �8σ, and another for �12σ.
As we show in the temporal performance calculations, the virtual effective throughput for navigation is high enough that it will be possible to implement MassRAM not only as a shared network resource, but eventually, as virtual memory using hard sequential storage. That is, because the hyperspace trees are fixed and space-filling for a given problem domain, the RAM transaction volume is low, with little random access. Thus, by using JINI technology (for example) over shared network resources, NVSI v2.0 can use FIFO paging from optimized disk storage, performing a look-ahead page-fetch in 16 GB (or larger) segments, while still not slowing the Navigation Manager. Under such an operating system, Mem is virtually unbounded, and we could realistically process 1012 nodes (which still only requires a 40-bit address) or more.
Temporal Parameters
Performance of the NVSI is partitioned into the two primary phases: the time Tpop to populate (compute and fill all the state-vectors in) the state-space, and the time Tnav to navigate the space (evaluate the domain collection—such as a financial portfolio—at each scenario, and flag selected nodes for states that meet the criteria).
The key to the NVSI idea is that the apparent (effective) throughput in response to a user query is driven by the navigation-time, as the population-time reflects background (off-line) computing.
As a reference, performance parameters are derived for the RiskScape problem domain, using the benchmark proxy already described.
The population time has four principle components:
1. A one-time setup by the Instantiation Manager;
2. A one-time pre-computation of the parametric-hypercubes for all relevant pricing models;
3. A recurring (for each daily update, as the portfolio is aged) recalculation of all values in V for every node in H; and
4. Background I/O and network-sharing overhead, which varies according to the amount of real-world data capture, and the size of H.
It is the third component that is most characteristic of Tpop. For our benchmark proxy, the calculation requirements for each of the <s values is:
j: 3 integer operations (
k: 1
z: 8
P(s): 1 lookup (˜1
n: 1 lookup & store ˜1
For V, the calculation times are highly varied. The cash variable requires 1
The total FLOPs, Fpop(3), to populate all nodes is then:
F pop(3)=Ω*53
We take as a baseline-reference CPU a typical mid-range, stand-alone workstation, with a computational throughput of R=107
T pop(3)=(53�109
To calculate the pre-computation time for the various pricing-model parametric-hypercubes, we require the characteristic computation time for typical models, and a choice of granularity in the parameter space. For Black-Scholes options, computing one price and the associated moments (Δ, Γ, vega, Θ, ρ, τ) takes ˜70 FLOP; one barrier or lookback option & moments: �1000 FLOP, and one exotic derivative (such as Black-Derman-Toy or Heath-Jarrow-Morton): ˜2,000-20,000
One of each type is needed for the benchmark proxy. Assuming three parameters for each (actually, six is more appropriate for exotic derivatives, but the hypercube becomes enormous, so each point is made a vector that embeds a family of curves), and assuming a granularity of 100 increments per parameter (dimension), then
the number of points for each parametric-hypercube=106 (1 million).
The total computation to create a Type 1 hypercube is thus 70�106
Thus, the amount Fpop(2) of parametric-hypercube precalculation is dominated by the exotics,
F pop(2)=
For the 10MFLOP CPU, this yields
T pop(2)=2100 seconds˜� hour.
If we estimate the Instantiation time Tpop(1) at about the same (to fill all the tables, some with millions of entries), ˜� hour, and that system overhead (category 4) doubles all the other times, then we have:
T pop(once)=2�[T pop(1)+T pop(2)+T pop(3)]≅5 hours, and
T pop(recurring)=2�T pop(3)=3 hours.
That is, the entire hyperspace H of states can be repopulated daily, allowing for real-time aging of the portfolio.
Navigation of H is the process of evaluating (pricing fully) the entire portfolio over the entire scenario-tree, and flagging the nodes (states) that satisfy the client-user query (on both probabilities and values). The Navigation time, Tnav, is thus dominated by the time required to price the portfolio, which entails pricing each instrument, and summing over the entire collection. Pricing an instrument involves calculating the virtual price (and all moments) from the proxy, and transforming with known multiplier coefficients (scaling, α and correlation, β). Doing this in turn requires taking each value stored in V (usually a set of input variables I), combining it with the free parameters of the instrument (such as X & T for a Black-Scholes option), and calculating the relevant selection parameters, used to either access a parametric-hypercube, or for newer instruments or open-form models, to calculate the final function output directly.
The process of evaluating the portfolio price for one scenario, that is, for one node (state) in the scenario-tree, we term mark-to-scenario (m-t-s). Evaluation of the portfolio over all scenarios, we term mark-to-landscape (m-t-l).
Flagging a node involves only two compares and a bit-flip in z, so Tnav≅Tm-t-l, which is given by:
T m-t-l =[T price �ω+T sum ]�M,
One of the essential aspects of the NVSI architecture is that, because the function-spaces are pre-computed (during the populate phase), the time to extract the price-values is nearly independent of model complexity. Instead, evaluation time is dependent on the number of parameters required to calculate for extraction of the proxy price.
Of course, the cash and futures values are stored in s directly, so pricing their corresponding instruments is trivial. Thus, a more realistic estimate is obtained by calculating the Tprice for the options, all of which are comparable to each other.
For the Type 1 option, the three parameters for extracting the price (and any other moment) are: {K/S, (r−δ)T, σ√T}. Each parameter requires about 1-2
Thus, to price all eight moments (p, and 7 greeks, for advanced models) of an actual option instrument, the amount of computation required (in FLOPS), Fprice, is given by:
F price=(4+8)
For a 1M (ω=106) instrument portfolio, the FLOPS to mark the entire portfolio to all scenarios for our benchmark is then:
The computation required to fully risk-evaluate a 1 million instrument portfolio over an entire scenario tree (κ=12, τ=6) is: 39 T
On the reference CPU, the time required is then:
T m-t-l =F m-t-l /R=(39�1012
At this point, two key components of the NVSI come into play:
Recall that the client-user measures performance in terms of the response to query, that is, on-demand access to H over all scenarios. Thus, we calculate an effective (virtual) throughput for this computation, optimized for portfolio risk-analysis with 100 shared reference-CPUs (in terms of virtual-FLOPS, or VFLOPS) as:
R NVSI(Risk Domain/100)=/F m-t-l /T nav=39T
A bounded spectrum for performance (in units of GVFLOPS) is then:
Note that the value for 1 CPU assumes a dedicated machine.
Comparison with Commercial Solutions
For comparison, if one were to simply "scale-up" existing instrument-valuation software, and run it on the best mainframe (dedicated hardware supercomputer) available, then a similar calculation to the above would involve very different computation times for different instruments. If we assume a typical global portfolio with 1M instruments, and a mix of 50% Type 1, 40% Type 2 and 10% Type 6, then the total computational demand is given by:
A CRAY T3E Supercomputer has a peak (burst) throughput of ˜2.2 T
T nav(CRAY T3E)=(7587�1012
On a more affordable (and obtainable for a financial institution) CRAY T90 (for which we estimate in this problem space a sustainable R ˜18 G
The most straightforward measure of price/performance is simply cost/R. The projected cost of version 1.0 of NVSI is ˜$10M. The cost of a fully-populated CRAY T90 is ˜$20M, and a fully-populated CRAY T3E ˜$100M. Thus:
Therefore, the NVSI is about 10 times more cost-effective than the only other machine that can solve the problem in reasonable time. And this does not even include the extended costs for the CRAY machine of software development (including staff), machine-room support, & depreciation.
In contrast, all of our NVSI calculations have been conservative: in MassRAM use, problem-complexity, structural-requirements, estimated calculation times, and network sharing & resources.
With these factors considered, we project that the cost of an NVSI implementation will be 50-100 times less than any comparable hardware-based commercial solution.
What have we really achieved? In theoretical terms the three fundamental breakthroughs are:
|Cited Patent
|Filing date
|Publication date
|Jan 6, 1982
|Jul 24, 1984
|Hitachi, Ltd.
|Job processing method utilizing a plurality of information processing devices
|Jun 25, 1981
|Aug 28, 1984
|At&T Bell Laboratories
|Data structure and search method for a data base management system
|Mar 1, 1989
|Dec 10, 1991
|The United States Of America As Represented By The United States Department Of Energy
|Method for simultaneous overlapped communications between neighboring processors in a multiple
|Feb 10, 1986
|Feb 11, 1992
|Hitachi, Ltd.
|Virtual machine file control system which translates block numbers into virtual addresses then into real addresses for accessing main storage
|Sep 27, 1989
|Mar 31, 1992
|Hitachi, Ltd.
|Virtual machine system having a plurality of real instruction processors and virtual machines, and a registration table
|Sep 14, 1993
|Sep 3, 1996
|Hitachi, Ltd.
|Virtual machine control method and virtual machine system
|Mar 31, 1994
|Nov 25, 1997
|Nec Research Institute, Inc.
|Software architecture for control of highly parallel computer systems
|Dec 12, 1996
|Sep 1, 1998
|Virtual Computer Corporation
|Computer network of distributed virtual computers which are EAC reconfigurable in response to instruction to be executed
|Mar 28, 1997
|Jul 20, 1999
|International Business Machines Corporation
|Managing processor resources in a multisystem environment in order to provide smooth real-time data streams, while enabling other types of applications to be processed concurrently
|Aug 22, 1991
|Aug 10, 1999
|Sandia Corporation
|Methods for operating parallel computing systems employing sequenced communications
|Jul 2, 1996
|Aug 31, 1999
|Compbionics, Inc.
|Cluster of workstations for solving compute-intensive applications by exchanging interim computation results using a two phase communication protocol
|Jul 29, 1997
|Aug 31, 1999
|Lincom Corporation
|Apparatus and method for data transfers through software agents using client-to-server and peer-to-peer transfers
|Dec 30, 1996
|Nov 16, 1999
|J.D. Edwards World Source Company
|System and method for managing the configuration of distributed objects
|Apr 24, 1997
|Dec 14, 1999
|Sun Microsystems, Inc.
|Method and system for distributed processing of applications on host and peripheral devices
|Sep 11, 1997
|Dec 14, 1999
|Nec Corporation
|Virtual group information managing method in bridge for network connection
|Feb 26, 1998
|Apr 4, 2000
|Sap Aktiengesellschaft
|Fast string searching and indexing using a search tree having a plurality of linked nodes
|Jan 17, 1997
|Sep 12, 2000
|Personal Agents, Inc.
|Intelligent agents for electronic commerce
|Jun 19, 1997
|Jul 31, 2001
|Novell, Inc.
|Multi-processor scheduling kernel
|Mar 4, 1999
|May 28, 2002
|Peter Biffar
|Self-learning and self-personalizing knowledge search engine that delivers holistic results
|Nov 30, 1998
|Jun 25, 2002
|Compaq Information Technologies Group, Lp
|Dynamic query expansion
|Jul 15, 1998
|Jul 16, 2002
|S. L. I. Systems, Inc.
|Search engine
|Aug 6, 2001
|Jan 4, 2005
|Infoglide Corporation
|System and method for comparing heterogeneous data sources
|Mar 15, 2001
|Dec 13, 2001
|Atsushi Hanai
|Online shopping system and method
|Jan 18, 2002
|Oct 24, 2002
|Globalserve Computer Services, Ltd.
|Electronic procurement
|Aug 8, 2002
|Mar 27, 2003
|Berkowitz Gary Charles
|Knowledge-based e-catalog procurement system and method
|Aug 5, 2003
|Jul 1, 2004
|Lalitha Vaidyanathan
|System and method for resolving a dispute in electronic commerce and managing an online dispute resolution process
|Sep 2, 2003
|Mar 3, 2005
|Vaidhyanathan Venkiteswaran
|Method and system using intelligent agents for dynamic integration of buy-side procurement systems with non-resident, web-enabled, distributed, remote, multi-format catalog sources
|Apr 2, 2004
|Oct 6, 2005
|Vadon Eric R
|Automated detection of associations between search criteria and item categories based on collective analysis of user activity data
|May 4, 2005
|Dec 8, 2005
|Yahoo! Inc.
|Systems and methods for identifying and extracting data from HTML pages
|Jan 3, 2005
|Jul 6, 2006
|Microsoft Corporation
|Method and apparatus for providing foreign language text display when encoding is not available
|Jul 13, 2007
|Jan 31, 2008
|Eplus Inc.
|System and method for creation and maintenance of a rich content or content-centric electronic catalog
|Aho, V. A., et al., "The Design and Analysis of Computer Algorithms," 1974, Reading, MA: Addison-Wesley, pp. 1-7.
|Hillis, W. D. "The Connection Machine," 1985, Cambridge: MIT Press, pp. 1-6.
|Hull, J. C. "Options, Futures, and Other Derivative Securities (2nd Ed).," 1993, Englewood Cliffs: Prentice-Hall, p. 1-9.
|Jorion, P. "Value at Risk," 1997, New York: McGraw-Hill, pp. 1-4.
|Knuth, D. E. "The Art of Computer Programming.," 1968, Reading, MA: Addison-Wesley, pp. 1-8.
|Lawrence, D. "Measuring and Managing Derivative Market Risk," 1996, London: ITP, pp. 1-6.
|Citing Patent
|Filing date
|Publication date
|Feb 14, 2011
|Oct 4, 2011
|Mordecai David K A
|System and method for dynamic path- and state-dependent stochastic control allocation
|Aug 8, 2002
|Aug 21, 2012
|Gary Charles Berkowitz
|Knowledge-based e-catalog procurement system and method
|Jun 28, 2010
|Sep 18, 2012
|Gary Charles Berkowitz
|Virtual supercomputer
|Dec 20, 2010
|Dec 25, 2012
|International Business Machines Corporation
|Task-based multi-process design synthesis with reproducible transforms
|May 15, 2009
|Jan 1, 2013
|Universiteit Gent
|Parameterized configuration for a programmable logic device
|Dec 20, 2010
|Mar 5, 2013
|International Business Machines Corporation
|Task-based multi-process design synthesis with notification of transform signatures
|Dec 20, 2010
|Mar 26, 2013
|International Business Machines Corporation
|Task-based multi-process design synthesis
|Oct 31, 2011
|Apr 16, 2013
|Prowness Consulting, LLC
|Method and system for modularizing windows imaging format
|Aug 9, 2007
|Mar 11, 2014
|Prowess Consulting, Llc
|Methods and systems for deploying hardware files to a computer
|Mar 5, 2013
|Mar 18, 2014
|International Business Machines Corporation
|Task-based multi-process design synthesis
|Mar 27, 2008
|Apr 22, 2014
|Siemens Aktiengesellschaft
|Image processing system for an x-ray installation
|Nov 22, 2010
|Jul 22, 2014
|Ca, Inc.
|System and method for capacity planning for systems with multithreaded multicore multiprocessor resources
|Oct 3, 2011
|Aug 19, 2014
|David K. A. Mordecai
|System and method for dynamic path- and state-dependent stochastic control allocation
|Nov 16, 2012
|Aug 11, 2015
|Amazon Technologies, Inc.
|Data estimation of historical data that identifies fine grained time period data and coarse grained time period data and applies correlated slopes to time periods
|Jul 21, 2014
|Sep 20, 2016
|Ca, Inc.
|System and method for capacity planning for systems with multithreaded multicore multiprocessor resources
|Jun 26, 2014
|Jan 10, 2017
|International Business Machines Corporation
|Operating programs on a computer cluster
|Nov 7, 2006
|Jan 17, 2017
|Prowess Consulting, Llc
|System and method for deploying a virtual machine
|Apr 3, 2012
|Jul 11, 2017
|Samsung Electronics Co., Ltd.
|Virtual architecture generating apparatus and method, and runtime system, multi-core system and methods of operating runtime system and multi-core system
|Aug 8, 2002
|Mar 27, 2003
|Berkowitz Gary Charles
|Knowledge-based e-catalog procurement system and method
|Nov 7, 2006
|Oct 4, 2007
|Prowess Consulting Llc
|System and method for deploying a virtual machine
|Nov 8, 2006
|Oct 4, 2007
|Prowess Consulting, Llc
|System and method for sanitizing a computer program
|Mar 27, 2008
|Oct 2, 2008
|Siemens Aktiengessellschaft
|Image processing system for an x-ray installation
|Aug 9, 2007
|Feb 12, 2009
|Prowess Consulting, Llc
|Methods and systems for deploying hardware files to a computer
|May 10, 2010
|Dec 9, 2010
|Noonan Iii Donal Charles
|System and method for capturing, managing, and distributing computer files
|Jun 28, 2010
|Jan 6, 2011
|Gary Charles Berkowitz
|Virtual Supercomputer
|May 15, 2009
|Mar 31, 2011
|Karel Bruneel
|Parameterized configuration for a programmable logic device
|Feb 14, 2011
|Jun 9, 2011
|Mordecai David K A
|System and method for dynamic path- and state-dependent stochastic control allocation
|Mar 29, 2011
|Sep 1, 2011
|International Business Machines Corporation
|Method, Apparatus And Computer Program Product Providing Instruction Monitoring For Reduction Of Energy Usage
|Nov 22, 2010
|May 24, 2012
|Zink Kenneth C
|System and method for capacity planning for systems with multithreaded multicore multiprocessor resources
|Jun 7, 2011
|Dec 13, 2012
|Tall Iv Charles H
|System and Method for Delegated Pricing and Quote Maintenance for Trading of Dependent Financial Instruments
|Apr 3, 2012
|May 2, 2013
|Samsung Electronics Co., Ltd.
|Virtual architecture generating apparatus and method, and runtime system, multi-core system and methods of operating runtime system and multi-core system
|Sep 10, 2014
|Apr 9, 2015
|International Business Machines Corporation
|Operating Programs on a Computer Cluster
|Jun 26, 2014
|Apr 9, 2015
|International Business Machines Corporation
|Operating Programs on a Computer Cluster
|Sep 30, 2014
|Mar 31, 2016
|Amazon Technologies, Inc.
|Dynamic code deployment and versioning
|U.S. Classification
|International Classification
|Cooperative Classification
|European Classification