Massachusetts Institute of Technology

Broadcom Corporation

Arvind Mithal

Lawrence S Rogel

James C Hoe

Xiaowei Shen

Hari Balakrishnan

Daniel L Rosenband

Srinivas Devadas

Michal Karczmarek

Muralidaran Vijayaraghavan

Enabling scheduling of single cycle as well as scheduling multi-cycle rules in a synchronous digital system whose behavior is governed by an asynchronous system specification (e.g., a TRS) provides a way to allow complex actions at state transitions of the asynchronous system without requiring that the complex actions be synthesized in logic that must be performed in a single clock cycle. For example, a relatively infrequent action may include a critical timing path that determines the maximum clock frequency of the system. By allowing that infrequent action to take multiple clock cycles, even if that action takes more absolute time, other actions may take less absolute time by virtue of being able to operate the synchronous system at a higher clock rate. The overall system may then operate more quickly (e.g., as measured by the average number of rules applied per unit of absolute time).

Hardware synthesis from multicycle rules

A method for specifying and synthesizing a synchronous digital circuit by first accepting a specification of an asynchronous system in which stored values are updated according to a set of state transition rules. For instance, the state transition rules are specified as a Term Rewriting System (TRS) in which each rule specifies a number of allowable state transitions, and includes a logical precondition on the stored values and a functional specification of the stored values after a state transition in terms of the stored values prior to the state transition. The specification of the asynchronous circuit is converted into a specification of a synchronous circuit in which a number of state transitions can occur during each clock period. The method includes identifying sets of state transitions, for example by identifying sets of TRS rules, that can occur during a single clocking period and forming the specification of the synchronous circuit to allow any of the state transitions in a single set to occur during any particular clocking period.

Synchronous circuit synthesis using an asynchronous specification

A method for selecting a queue for service across a shared link. The method includes classifying each queue from a group of queues within a plurality of ingresses into one tier of a number 'N' of tiers. The number 'N' is greater than or equal to 2. Information about allocated bandwidth is used to classify at least some of the queues into the tiers. Each tier is assigned a different priority. The method also includes matching queues to available egresses by matching queues classified within tiers with higher priorities before matching queues classified within tiers with lower priorities.

Method and apparatus for bandwidth guarantee and overload protection in a network switch

A scheduling approach enables scheduling sequential execution of rules in a single cycle of a synchronous system without necessarily requiring explicit implementation of a composite rule for each sequence of rules than may be composed. One method for designing a synchronous digital system includes using modules with multiple successive interfaces such that within the a single clocked cycle, each module performs a function equivalent to completing interactions through one of its interfaces before performing interactions through any succeeding one of its interfaces. The scheduled state transition rules are associated with corresponding interfaces of the modules.

Circuit synthesis with sequential rules

A computer architecture that includes a hierarchical memory system and one or more processors. The processors execute memory access instructions whose semantics are defined in terms of the hierarchical structure of the memory system. That is, rather than attempting to maintain the illusion that the memory system is shared by all processors such that changes made by one processor are immediately visible to other processors, the memory access instructions explicitly address access to a processor-specific memory, and data transfer between the processor-specific memory and the shared memory system. Various alternative embodiments of the memory system are compatible with these instructions. These alternative embodiments do not change the semantic meaning of a computer program which uses the memory access instructions, but allow different approaches to how and when data is actually passed from one processor to another.

Computer architecture for shared memory access

A method for specifying and synthesizing a synchronous digital circuit by first accepting a specification of an asynchronous system in which stored values are updated according to a set of state transition rules. For instance, the state transition rules are specified as a Term Rewriting System (TRS) in which each rule specifies a number of allowable state transitions, and includes a logical precondition on the stored values and a functional specification of the stored values after a state transition in terms of the stored values prior to the state transition. The specification of the asynchronous circuit is converted into a specification of an synchronous circuit in which a number of state transitions can occur during each clock period. The method includes identifying sets of state transitions, for example by identifying sets of TRS rules, that can occur during a single clocking period and forming the specification of the synchronous circuit to allow any of the state transitions in a single set to occur during any particular clocking period.

Digital circuit synthesis system

A methodology for designing a distributed shared-memory system, which can incorporate adaptation or selection of cache protocols during operation, guarantees semantically correct processing of memory instructions by the multiple processors. A set of rules includes a first subset of &ldquo;mandatory&rdquo; rules and a second subset of &ldquo;voluntary&rdquo; rules such that correct operation of the memory system is provided by application of all of the mandatory rules and selective application of the voluntary rules. A policy for enabling voluntary rules specifies a particular coherent cache protocol. The policy can include various types of adaptation and selection of different operating modes for different addresses and at different caches. A particular coherent cache protocol can make use of a limited capacity directory in which some but not necessarily all caches that hold a particular address are identified in the directory. In another coherent cache protocol, various caches hold an address in different modes which, for example, affect communication between a cache and a shared memory in processing particular memory instructions.

Growing community of inventors

Arlington, MA, United States of America

Arvind Mithal