Altera Corporation

Solace Systems, Inc.

Silicon Access Networks, Inc.

Edward D Funnekotter

David Walter Carr

Paul Nadj

James Michael O'Connor

Jonathan L Bosloy

Jason Whelan

Charles Mitchell

Daniel Dwight Grove

Paul Kondrat

David W Horton

Stephen Cadieux

Philippe-Andre Babkine

Jon Huie

Patrick Brodeur

A method for high-speed scheduling and arbitration of events for computing and networking is disclosed. The method includes the software and hardware implementation of a unique data structure, known as a pile, for scheduling and arbitration of events. According to the method, events are stored in loosely sorted order in piles, with the next event to be processed residing in the root node of the pile. The pipelining of the insertion and removal of events from the piles allows for simultaneous event removal and next event calculation. The method's inherent parallelisms thus allow for the automatic rescheduling of removed events for re-execution at a future time, also known as event swapping. The method executes in O() time.

System and method for scheduling and arbitrating events in computing and networking

A method for high-speed scheduling and arbitration of events for computing and networking is disclosed. The method includes the software and hardware implementation of a unique data structure, known as a pile, for scheduling and arbitration of events. According to the method, events are stored in loosely sorted order in piles, with the next event to be processed residing in the root node of the pile. The pipelining of the insertion and removal of events from the piles allows for simultaneous event removal and next event calculation. The method's inherent parallelisms thus allow for the automatic rescheduling of removed events for re-execution at a future time, also known as event swapping. The method executes in O(1) time.

A method and apparatus for converting documents from one format to another in a speed efficient way involves a hardware module which implements several operating pipeline stages which work in parallel. The transformations are supplied and decomposed into sequences of control units. The transformation of documents consists of applying control unit sequences to input documents. The control units are themselves executed by a set of dedicated hardware resources. Furthermore the pipeline is capable of operating on more than one document at a time. Fast document transformation is a key capability of document processing systems. The use of parallel processing techniques and hardware that implements highly specialized transformation resources make this invention particularly scalable for its use in large, high speed content networks.

Transformation module for transforming documents from one format to other formats with pipelined processor having dedicated hardware resources

An improved data structure is provided by modifying a public-domain data structure known as a 'heap'. When these improvements are applied, the resultant data structure is known as a 'pile.' This invention further describes a pipelined hardware implementation of a pile. Piles offer many advantages over heaps: they allow for fast, pipelined hardware implementations with increased throughput, making piles practical for a wide variety of new applications; they remove the requirement to track and update the last position in the heap; they reduce the number of memory reads accesses required during a delete operation; they require only ordinary, inexpensive RAM for storage in a fast, pipelined implementation; and they allow a random mixture of back-to-back insert, remove, and swap operations to be performed without stalling the pipeline.

Data structure and method for pipeline heap-sorting

A method of matching subscriptions to published documents in a content-routed network involves receiving subscription information, receiving published documents, storing the subscription information and the published documents in memory, instructing an accelerator of the locations in memory of the published documents, transferring portions of the stored published documents from the memory to the accelerator on an as-needed basis, providing the subscription information to the accelerator, and processing the portions in the accelerator to perform subscription matching in the accelerator independently of other functions in the content-router. The accelerator preferably includes a pipeline. In this way, efficiently highly scalable subscription matching can be performed efficiently on a very large number of subscriptions.

Highly scalable subscription matching for a content routing network

An improved data structure is provided by modifying a public-domain data structure known as a 'heap'. When these improvements are applied, the resultant data structure is known as a 'pile.' This invention further described a pipelined hardware implementation of a pile. Piles offer many advantages over heaps: they allow for fast, pipelined hardware implementations with increased throughput, making piles practical for a wide variety of new applications; they remove the requirement to track and update the last position in the heap; they reduce the number of memory reads accesses required during a delete operation; they require only ordinary, inexpensive RAM for storage in a fast, pipelined implementation; and they allow a random mixture of back-to-back insert, remove, and swap operations to be performed without stalling the pipeline.

Data structure and method for sorting using heap-supernodes

The present invention provides the method and system that redistribute the nodes of a sorted tree to enable faster data insertion. Further, the tree typically contains a fixed number of levels, each comprising a fixed number of nodes. Each node in the tree is indexed and each leaf node may comprise a number of data segments. An increment is empirically calculated as space redistributed among non-empty leaf nodes. Furthermore, when a data segment is inserted and certain conditions are met, a data structure with a marked head and tail effectively 'traverses' the tree from one end to the other searching for empty leaf nodes. In cases where the data structure encounters an empty leaf node, the data structure continues traversing unless empirically determined conditions stipulate that the process halts until the next data segment insertion before continuing. Moreover, in cases where the data structure encounters a non-empty leaf node, the contents of the node are copied from the head to the tail of the data structure. When the node has been copied, the data structure updates the tree to ensure that a lookup operation on the copied node remains valid and that the invariants of the tree hold before and after the redistribution. Furthermore, the contents in the head of the data structure are then deleted and the tail advanced to leave an increment amount of empty spaces in the traveling direction. The traversal process may then follow one of two possible paths of action: either continue traversing the tree or halt for the next data insertion before continuing.

Method and system for rapid insertion of various data streams into sorted tree structures

An embodiment of the present invention described and shown in the specification and drawing is a Ternary Content Addressable Memory (TCAM) multi-dimensional multi-way branch selector. The embodiment that is disclosed includes a wide TCAM and a pre-TCAM multi-field multi-mode comparator for coupling to a microprocessor for performing multi-way branching decisions based on multi-dimensional comparisons. It is emphasized that this abstract is provided to comply with the rule requiring an abstract which will allow a searcher or other reader to quickly ascertain the subject matter of the technical disclosure. It is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims.

Ternary content addressable memory based multi-dimensional multi-way branch selector and method of operating same

A method and means to reduce memory requirements for storing statistics by recording, in a separate overflow memory, the most significant bits of counters requiring more bits than provided in the main statistics memory. A binary CAM provides the linking mechanism between the main and overflow memories.

Growing community of inventors

Ottawa, Canada

Edward D Funnekotter