Bay Networks, Inc.

Nortel Networks Corporation

Edward S Harriman

Richard L Angle

Geoffrey B Ladwig

Heather D Achilles

Geoff B Ladwig

A system interconnect architecture and associated arbitration scheme that provides for the interleaving of multiple accesses to a shared system resource by multiple system components on a data block by data block basis. According to one embodiment, an access request is granted &ldquo;immediately&rdquo; upon receipt such that the effective access latency between an access request and the transfer of a first data block (e.g. a byte, a word, a long word, or a double long word as determined by the width or throughput of the data path) for the access is the minimum access latency to the shared system resource. If a second access request is received while a first access is being performed, the second access request is granted immediately, and the first and second accesses are thereafter interleaved such that data blocks of the accesses are alternately transferred by the system interconnect.

Data path architecture and arbitration scheme for providing access to a shared system resource

A method for handling cache misses in a computer system. A prefetch unit fetches an instruction for execution by one of a plurality of coprocessors. When the preferred embodiment of the present invention experiences a cache miss in a prefetch unit, the process for which an instruction is being fetched is passed off to a memory processor which executes a read of the missing cache line in memory. While the process is executing in memory processor, or queued by the scheduler for execution of the same instruction, the prefetch unit continues to dispatch other processes from the its queue to the other processors. Thus, the computer system, including the processors, do not stall. Processors continue to execute processes. The prefetch unit continues to dispatch processes. When the memory read is completed, the process in which the cache miss occurred is rescheduled by the scheduler. The prefetch again attempts to fetch and decode the instruction and arguments. If another cache miss occurs, the process is again dispatched to the memory processor. Upon reading the cache line, the memory processor again sends the process to the scheduler's queue.

Method and apparatus for handling cache misses in a computer system

A method and apparatus for maintaining an order of processing data packets. One embodiment of the invention includes a first stage of data packet processing, which sequentially receives a plurality of independent data packets. The data packet are to be processed at the first stage in parallel. The plurality of independent data packets are then permitted to continue processing at a separate stage only in the order the independent data packets were received at the first stage of the data packet processing. In one embodiment, the invention includes assigning a sequence number to a first independent data packet of the plurality of packets prior to the first stage of data packet processing. Thereafter, the invention includes comparing the sequence number assigned to the first independent data packet to a servicing number. In response to the sequence number and the servicing number being different by N, wherein N is an integer, the invention permits the first independent packet to continue processing at a separate stage. Thereafter, the servicing number is incremented by replacing the servicing number with the sequence number.

Method and apparatus for maintaining an order of data packets

A computer system architecture in which each processor has its own memory, strategically distributed along the stages of an execution pipeline of the processor, to provide fast access to often used information, such as the contents of the address and data registers, the program counter, etc. Memory storage is strategically located in close physical proximity to a stage in an execution pipeline at which memory is commonly or repeatedly accessed. Coupled to the pipeline at various stages are small memory cells for storing information that is consistently and repeatedly requested at that stage in the execution pipeline. The speed of the execution pipeline in a processor is critical to overall performance of the processor and the computer architecture of the present invention as a whole. To that end, the clock cycle time at which the pipeline is operated is increased as much as the operating characteristics of the logic and associated circuitry will allow. Generally, access times for memory are slower than the clock cycle times at which the pipeline logic can operate. Thus, there is a point of diminishing return at which increasing the clock cycle time of the pipeline is less advantageous if the pipeline must wait for memory access to complete. Thus, there is provided two sets of strategically located memory cells distributed along the execution pipeline of a processor, and alternately accesses the memory cells.

Distributed pipeline memory architecture for a computer system with even and odd pids

A method and apparatus for processing network packets is disclosed. A Single Instruction Multiple Data (SIMD) architecture processor is disclosed. The SIMD processor includes several instructions designed specifically for the task of network packet processing. For example, SIMD add instructions for performing one's complement additions are included to quickly calculate Internet checksums. Furthermore, the SIMD processor includes several instructions for performing lane arithmetic.

Method and apparatus for performing lane arithmetic to perform network

A system interconnect architecture and associated arbitration scheme that provides for the interleaving of multiple accesses to a shared system resource by multiple components on a data block by data block basis. According to one embodiment, an access request is granted 'immediately' upon receipt such that the effective access latency between an access request and the transfer of a first data block (e.g. a byte. a word, a long word, and a double long word as determined by the width or throughput of the data path) for the access is the minimum access latency to the shared system resource. If a second access request is received while a first access is being performed, the second access request is granted immediately, and the first and second access are thereafter interleaved such that data blocks of the accesses are alternately transferred by the system interconnect.

Data path architecture and arbitration scheme for providing access to a

A method for searching for keys of arbitrary width in a table in a memory of a computer system by repeatedly executing lookup instructions on a lookup processor. The lookup processor executes a lookup instruction to find a key in a table. The execution of the lookup instruction results in a key being found, or a key not being found. If the key is not found, the process is requeued by a scheduler with the program counter register for the process pointing to the instruction immediately following the lookup instruction, i.e., the next instruction. In the event the key is found in the table, the entry in the table associated with the key contains the memory address of the next instruction to be executed. This memory address is loaded into the program counter register associated with the process in which the lookup instruction was executed. The scheduler requeues the process, later dequeues it, and the instruction pointed to by the program counter register is fetched by an instruction fetch unit. A dispatcher sends the process to the appropriate processor for execution of the next instruction. In this way, a branch to any instruction in the process can be performed. The instruction pointed to by the PC register can be another lookup instruction in the process. In this way, multiple lookup instructions can be sequentially executed, each specifying a different portion of a key of arbitrary width, or each specifying a particular key in a sequence of keys being searched for.

Method for branching to an instruction in a computer program at a memory

In a search method for a radix search tree, a logic circuit for computing the actual offset of an entry in a node in a tree. The logic circuit accepts a pointer to a node in the tree, along with an associated bit mask indicating which entries are present in the node. The logic circuit further receives an entry value, the offset of which from the beginning of the node is to be computed by the logic circuit. The logic circuit utilizes Boolean AND gates to mask off higher order bits in the bit mask above the bit position corresponding to the entry value received by the logic circuit. The lower order bits in the bit mask, up to but not including the bit position corresponding to the entry value, are added together to determine the number of entries that exist at a lower offset in the node than the entry indicated by the entry value. The logic circuit combines the pointer received with the sum computed to calculate the offset memory address at which the entry is located in the node.

Radix tree search logic

A computer implemented method for searching for a key in a radix search tree in a memory of a computer system. A table of keys is organized in a radix search tree stored in a memory of a computer system. The keys are divided into a string of symbols. Each node in the tree corresponds to a symbol. A path from a root node to a leaf node at level n in the tree represents a string of n symbols comprising a key. Each node is capable of having m possible entries corresponding to m possible symbol values. Each entry comprises a pointer to a son node and an existence map indicating which entries exist in the son node. In the preferred embodiment, the existence map is a bit mask that indicates, based on bit positions enabled and disabled in the bit mask, which entries exist in the son node pointed to by the pointer. By providing an existence map along with the pointer to a son node, m memory locations for m entries are allocated for the son node only if all of the m possible entries are used. Memory locations for entries that would otherwise be empty are not allocated, thereby minimizing memory resources required by a radix search tree.

Method for storing a tree of potential keys in a sparse table

A multitasking computer system having multiple parallel and independently executing processors. Each processor has multiple pipeline stages. Each stage in the pipeline can be simultaneously executing a process. More processes than the sum of pipeline stages for all processors exist at any given time, which allows processes to migrate between processors and allows the processes queued at any one processor to increase, i.e., back up, momentarily without causing other processors to sit idle. Related to the ability to support at least as many processes as there are the sum of pipeline stages in all of the processors is the ability of the preferred embodiment of the present invention to migrate processes between processors. When a processor completes execution of an instruction for a particular process, the program counter for the process is incremented to point to the next instruction in the process. The process is then requeued by a scheduler. A instruction fetch unit fetches the next instruction and associated arguments, if any, and dispatches the process to the same or other processor for execution of the next instruction in the process. Thus, a process can migrate from one processor to another processor.

Method and apparatus for multitasking in a computer system

A pipeline processor having an add circuit configured to execute separate atomic add instructions in consecutive clock cycles, wherein each separate atomic add instructions can be updating the same memory address location. In one embodiment, the add circuit includes a carry-save-add circuit coupled to a set of carry propagate adder circuits. The carry-save-add circuit is configured to perform an add operation in one processor clock cycle and the set of carry propagate adder circuits are configured to propagate, in subsequent clock cycles, a carry generated by the carry-save-add circuit. The add circuit is further configured to feedforward partially propagated sums to the carry-save-add circuit as at least one operand for subsequent atomic add instructions. In one embodiment, the pipeline processor is implemented on a multitasking computer system architecture supporting multiple independent processors dedicated to processing data packets.

Growing community of inventors

Bedford, MA, United States of America

Edward S Harriman