US Patent No: 7,657,891

Number of patents in Portfolio can not be more than 2000

Multithreading microprocessor with optimized thread scheduler for increasing pipeline utilization efficiency

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

A multithreading processor for concurrently executing multiple threads is provided. The processor includes an execution pipeline and a thread scheduler that dispatches instructions of the threads to the execution pipeline. The execution pipeline detects a stalling event caused by a dispatched instruction, and flushes the execution pipeline to enable instructions of other threads to continue executing. The execution pipeline communicates to the scheduler which thread caused the stalling event, and the scheduler stops dispatching instructions for the thread until the stalling condition terminates. In one embodiment, the execution pipeline only flushes the thread including the instruction that caused the event. In one embodiment, the execution pipeline stalls rather than flushing if the thread is the only runnable thread. In one embodiment, the processor includes skid buffers to which the flushed instructions are rolled back so the instruction fetch pipeline need not be flushed, only the execution pipeline.

Loading the Abstract Image... loading....

First Claim

See full text

Family

Loading Family data... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
MIPS TECHNOLOGIES, INC.MOUNTAIN VIEW, CA64

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Jensen, Michael Gottlieb Sunnyvale, US 26 473
Jones, Darren M Los Altos, US 17 397
Kinter, Ryan C Sammamish, US 34 475
Vishin, Sanjay Sunnyvale, US 26 810

Cited Art Landscape

Patent Info (Count) # Cites Year
 
SONY COMPUTER ENTERTAINMENT INC. (1)
2006/0123,420 Scheduling method, scheduling apparatus and multiprocessor system 33 2005
 
HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP (3)
6,073,159 Thread properties attribute vector based thread selection in multithreading processor 63 1996
6,032,218 Configurable weighted round robin arbiter 68 1998
6,647,449 System, method and circuit for performing round robin arbitration 41 2000
 
DATA GENERAL CORPORATION (1)
5,745,778 Apparatus and method for improved CPU affinity in a multiprocessor system 274 1994
 
SAMSUNG ELECTRONICS CO., LTD. (2)
6,272,579 Microprocessor architecture capable of supporting multiple heterogeneous processors 86 1999
7,269,712 Thread selection for fetching instructions for pipeline multi-threaded processor 19 2004
 
ORACLE AMERICA, INC. (1)
7,185,178 Fetch speculation in a multithreaded processor 53 2004
 
NEC CORPORATION (1)
6,556,571 Fast round robin priority port scheduler for high capacity ATM switches 34 1999
 
INTELLECTUAL VENTURES I LLC (2)
5,793,993 Method for transmitting bus commands and data over two wires of a serial bus 85 1995
5,938,742 Method for configuring an intelligent low power serial bus 126 1995
 
RENESAS ELECTRONICS AMERICA, INC. (1)
* 5,860,000 Floating point unit pipeline synchronized with processor pipeline 25 1996
 
KABUSHIKI KAISHA TOSHIBA (3)
6,101,193 Packet scheduling scheme for improving short time fairness characteristic in weighted fair queueing 97 1997
2003/0182,536 Instruction issuing device and instruction issuing method 21 2002
2004/0139,441 Processor, arithmetic operation processing method, and priority determination method 33 2004
 
BROADCOM CORPORATION (1)
* 7,334,086 Advanced processor with system on a chip interconnect technology 54 2004
 
SYNOPSYS, INC. (1)
7,051,189 Method and apparatus for processor code optimization using code compression 31 2001
 
GOOGLE INC. (4)
6,076,157 Method and apparatus to force a thread switch in a multithreaded processor 186 1997
6,212,544 Altering thread priorities in a multithreaded processor 252 1997
* 6,694,425 Selective flush of shared and other pipeline stages in a multithread processor 69 2000
6,721,874 Method and system for dynamically shared completion table supporting multiple threads in a processing system 29 2000
 
MARVELL WORLD TRADE LTD. (1)
2006/0212,853 Real-time control apparatus having a multi-thread processor 59 2005
 
ALCATEL USA SOURCING, INC. (1)
6,434,155 Weighted round robin engine used in scheduling the distribution of ATM cells 40 1999
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (6)
6,105,051 Apparatus and method to guarantee forward progress in execution of threads in a multithreaded processor 69 1997
6,567,839 Thread switch control in a multithreaded processor system 195 1997
6,237,081 Queuing method and apparatus for facilitating the rejection of sequential instructions in a processor 19 1998
6,516,369 Fair and high speed arbitration system based on rotative and weighted priority monitoring 37 1999
* 7,096,470 Method and apparatus for implementing thread replacement for optimal performance in a two-tiered multithreading structure 22 2002
2006/0168,393 Apparatus and method for dependency tracking and register file bypass controls using a scannable register file 17 2005
 
ADVANCED MICRO DEVICES, INC. (1)
5,832,278 Cascaded round robin request selection method and apparatus 63 1997
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (4)
* 5,067,069 Control of multiple functional units with parallel operation in a microcoded execution unit 84 1989
5,095,460 Rotating priority encoder operating by selectively masking input signals to a fixed priority encoder 27 1989
6,918,116 Method and apparatus for reconfiguring thread scheduling using a thread scheduler function unit 19 2001
2006/0168,254 Automatic policy selection 29 2004
 
LUCENT TECHNOLOGIES INC. (1)
7,007,153 Method and apparatus for allocating functional units in a multithreaded VLIW processor 21 2000
 
EXTREME NETWORKS, INC. (1)
5,898,694 Method of round robin bus arbitration 37 1996
 
CISCO TECHNOLOGY, INC. (1)
7,441,101 Thread-aware instruction fetching in a multithreaded embedded processor 21 2004
 
ENTERASYS NETWORKS, INC. (1)
5,528,513 Scheduling and admission control policy for a continuous media server 216 1993
 
GLOBALFOUNDRIES INC. (1)
6,563,818 Weighted round robin cell architecture 56 1999
 
THOMSON LICENSING (1)
2005/0076,189 Method and apparatus for pipeline processing a chain of processing instructions 18 2004
 
ROCKWELL TECHNOLOGIES, LLC (1)
6,665,760 Group shifting and level shifting rotational arbiter system 34 2000
 
Modular Computer Systems, Inc. (1)
4,924,380 Dual rotating priority arbitration method for a multiprocessor memory bus 54 1988
 
FUJITSU LIMITED (1)
6,754,736 Information processing apparatus, data inputting/outputting method, and program storage medium therefor 24 2000
 
SUN MICROSYSTEMS, INC. (4)
* 5,546,554 Apparatus for dynamic register management in a floating point unit 73 1994
6,094,435 System and method for a quality of service in a multi-layer network element 179 1997
6,295,600 Thread switch on blocked load or store using instruction thread field 80 1999
2006/0004,989 Mechanism for selecting instructions for execution in a multithreaded processor 28 2004
 
GATEWAY, INC. (1)
5,276,887 Bus arbitration system for granting bus access to devices following two-wire bus arbitration protocol and devices following three-wire bus arbitration protocol 40 1991
 
ROUND ROCK RESEARCH, LLC (1)
6,170,051 Apparatus and method for program level parallelism in a VLIW processor 147 1997
 
FORCE 10 NETWORKS, INC. (1)
6,868,529 Method and apparatus for efficient implementation of round robin control unit 21 2001
 
EMC CORPORATION (1)
6,105,053 Operating system for a non-uniform memory access multiprocessor system 152 1995
 
INTEL CORPORATION (9)
5,357,512 Conditional carry scheduler for round robin scheduling 28 1992
6,658,447 Priority based simultaneous multi-threading 113 1997
6,272,520 Method for detecting thread switch events 98 1997
6,542,921 Method and apparatus for controlling the processing priority between multiple threads in a multithreaded processor 62 1999
6,609,190 Microprocessor with primary and secondary issue queue 24 2000
6,385,715 Multi-threading for a processor utilizing a replay queue 70 2001
6,792,446 Storing of instructions relating to a stalled thread 30 2002
2003/0233,394 Method and apparatus for ensuring fairness and forward progress when executing multiple threads of execution 44 2002
2004/0128,448 Apparatus for memory communication during runahead execution 38 2002
 
MIPS TECHNOLOGIES, INC. (4)
5,309,382 Binary shifter 27 1992
5,734,877 Processor chip having on-chip circuitry for generating a programmable external clock signal and for controlling data patterns 32 1996
2006/0179,274 Instruction/skid buffers in a multithreading microprocessor 24 2005
2006/0179,279 Bifurcated thread scheduler in a multithreading microprocessor 29 2005
 
HTC CORPORATION (1)
6,549,930 Method for scheduling threads in a multithreaded processor 109 1997
 
STMICROELECTRONICS S.R.L. (1)
6,633,939 Variable-priority arbitration method and respective system 20 2001
 
MICROVISION, INC. (1)
7,120,714 High-speed starvation-free arbiter system, rotating-priority arbiter, and two stage arbitration method 38 2003
 
Texas Instruments Incorporated (3)
5,913,049 Multi-stream complex instruction set microprocessor 80 1997
2006/0095,732 Processes, circuits, devices, and systems for scoreboard and other processor improvements 61 2005
2007/0204,137 Multi-threading processors, integrated circuit devices, systems, and processes of operation and manufacture 51 2006
 
FLOW WISE NETWORKS INC. (1)
6,163,827 Method and apparatus for round-robin flash channel arbitration 18 1997
 
NVIDIA CORPORATION (2)
7,015,913 Method and apparatus for multithreaded processing of data in a programmable graphics processor 80 2003
* 6,987,517 Programmable graphics processor for generalized texturing 20 2004
 
ARM FINANCE OVERSEAS LIMITED (11)
6,477,562 Prioritized instruction scheduling for multi-streaming processors 107 1998
6,389,449 Interstream control and communications for multi-streaming digital processors 107 1999
2002/0083,173 Method and apparatus for optimizing selection of available contexts for packet processing in multi-stream packet processing 61 2001
2006/0179,280 Multithreading processor including thread scheduler based on instruction stall likelihood prediction 32 2005
2006/0179,439 Leaky-bucket thread scheduler in a multithreading microprocessor 23 2005
* 7,490,230 Fetch director employing barrel-incrementer-based round-robin apparatus for use in multithreading microprocessor 15 2005
2008/0069,115 BIFURCATED TRANSACTION SELECTOR SUPPORTING DYNAMIC PRIORITIES IN MULTI-PORT SWITCH 18 2006
2008/0069,128 TRANSACTION SELECTOR EMPLOYING BARREL-INCREMENTER-BASED ROUND-ROBIN APPARATUS SUPPORTING DYNAMIC PRIORITIES IN MULTI-PORT SWITCH 17 2006
2008/0069,129 TRANSACTION SELECTOR EMPLOYING ROUND-ROBIN APPARATUS SUPPORTING DYNAMIC PRIORITIES IN MULTI-PORT SWITCH 19 2006
2008/0069,130 TRANSACTION SELECTOR EMPLOYING TRANSACTION QUEUE GROUP PRIORITIES IN MULTI-PORT SWITCH 17 2006
2007/0113,053 MULTITHREADING INSTRUCTION SCHEDULER EMPLOYING THREAD GROUP PRIORITIES 29 2007
 
Nomadix, Inc. (1)
6,810,426 Methods and systems providing fair queuing and priority scheduling to enhance quality of service in a network 109 2002
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
6,105,127 Multithreaded processor for processing multiple instruction streams independently of each other by flexibly controlling throughput in each instruction stream 114 1997
 
NORTEL NETWORKS LIMITED (1)
6,470,016 Servicing output queues dynamically according to bandwidth allocation in a frame environment 98 1999
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
SOCIONEXT INC. (2)
* 8,001,549 Multithreaded computer system and multithread execution control method 4 2007
* 2007/0266,387 MULTITHREADED COMPUTER SYSTEM AND MULTITHREAD EXECUTION CONTROL METHOD 9 2007
 
MIPS TECHNOLOGIES, INC. (3)
7,853,777 Instruction/skid buffers in a multithreading microprocessor that store dispatched instructions to avoid re-fetching flushed instructions 3 2005
* 2006/0179,274 Instruction/skid buffers in a multithreading microprocessor 24 2005
8,151,268 Multithreading microprocessor with optimized thread scheduler for increasing pipeline utilization efficiency 1 2010
 
ARM FINANCE OVERSEAS LIMITED (4)
8,078,840 Thread instruction fetch based on prioritized selection from plural round-robin outputs for different thread states 5 2008
* 2009/0113,180 Fetch Director Employing Barrel-Incrementer-Based Round-Robin Apparatus For Use In Multithreading Microprocessor 4 2008
* 2009/0249,351 Round-Robin Apparatus and Instruction Dispatch Scheduler Employing Same For Use In Multithreading Microprocessor 6 2009
* 2009/0271,592 Apparatus For Storing Instructions In A Multithreading Microprocessor 6 2009
* Cited By Examiner

Maintenance Fees

Fee Large entity fee small entity fee micro entity fee due date
7.5 Year Payment $3600.00 $1800.00 $900.00 Aug 2, 2017
11.5 Year Payment $7400.00 $3700.00 $1850.00 Aug 2, 2021
Fee Large entity fee small entity fee micro entity fee
Surcharge - 7.5 year - Late payment within 6 months $160.00 $80.00 $40.00
Surcharge - 11.5 year - Late payment within 6 months $160.00 $80.00 $40.00
Surcharge after expiration - Late payment is unavoidable $700.00 $350.00 $175.00
Surcharge after expiration - Late payment is unintentional $1,640.00 $820.00 $410.00