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

ALSO PUBLISHED AS: 20060179284

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

all claims..

Family

Loading Family data... loading....

Patent Owner(s)

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

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Jensen, Michael Gottlieb Holte, DK 46 411
Jones, Darren M Los Altos, CA 33 338
Kinter, Ryan C Los Altos, CA 61 394
Vishin, Sanjay Sunnyvale, CA 39 752

Cited Art Landscape

Patent Info (Count) # Cites Year
 
ARM FINANCE OVERSEAS LIMITED (11)
6,477,562 Prioritized instruction scheduling for multi-streaming processors 100 1998
6,389,449 Interstream control and communications for multi-streaming digital processors 103 1999
2002/0083,173 Method and apparatus for optimizing selection of available contexts for packet processing in multi-stream packet processing 58 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 21 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 27 2007
 
INTEL CORPORATION (9)
5,357,512 Conditional carry scheduler for round robin scheduling 26 1992
6,658,447 Priority based simultaneous multi-threading 96 1997
6,272,520 Method for detecting thread switch events 91 1997
6,542,921 Method and apparatus for controlling the processing priority between multiple threads in a multithreaded processor 59 1999
6,609,190 Microprocessor with primary and secondary issue queue 19 2000
6,385,715 Multi-threading for a processor utilizing a replay queue 63 2001
6,792,446 Storing of instructions relating to a stalled thread 29 2002
2003/0233,394 Method and apparatus for ensuring fairness and forward progress when executing multiple threads of execution 37 2002
2004/0128,448 Apparatus for memory communication during runahead execution 32 2002
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (7)
* 5,067,069 Control of multiple functional units with parallel operation in a microcoded execution unit 83 1989
5,095,460 Rotating priority encoder operating by selectively masking input signals to a fixed priority encoder 27 1989
6,073,159 Thread properties attribute vector based thread selection in multithreading processor 60 1996
6,032,218 Configurable weighted round robin arbiter 60 1998
6,647,449 System, method and circuit for performing round robin arbitration 40 2000
6,918,116 Method and apparatus for reconfiguring thread scheduling using a thread scheduler function unit 17 2001
2006/0168,254 Automatic policy selection 23 2004
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (6)
6,105,051 Apparatus and method to guarantee forward progress in execution of threads in a multithreaded processor 68 1997
6,567,839 Thread switch control in a multithreaded processor system 184 1997
6,237,081 Queuing method and apparatus for facilitating the rejection of sequential instructions in a processor 18 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 20 2002
2006/0168,393 Apparatus and method for dependency tracking and register file bypass controls using a scannable register file 17 2005
 
SUN MICROSYSTEMS, INC. (5)
* 5,546,554 Apparatus for dynamic register management in a floating point unit 65 1994
6,094,435 System and method for a quality of service in a multi-layer network element 169 1997
6,295,600 Thread switch on blocked load or store using instruction thread field 77 1999
2006/0004,989 Mechanism for selecting instructions for execution in a multithreaded processor 25 2004
7,185,178 Fetch speculation in a multithreaded processor 49 2004
 
GOOGLE INC. (4)
6,076,157 Method and apparatus to force a thread switch in a multithreaded processor 171 1997
6,212,544 Altering thread priorities in a multithreaded processor 240 1997
* 6,694,425 Selective flush of shared and other pipeline stages in a multithread processor 65 2000
6,721,874 Method and system for dynamically shared completion table supporting multiple threads in a processing system 29 2000
 
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 26 2005
 
KABUSHIKI KAISHA TOSHIBA (3)
6,101,193 Packet scheduling scheme for improving short time fairness characteristic in weighted fair queueing 95 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 30 2004
 
TEXAS INSTRUMENTS INCORPORATED (3)
5,913,049 Multi-stream complex instruction set microprocessor 76 1997
2006/0095,732 Processes, circuits, devices, and systems for scoreboard and other processor improvements 50 2005
2007/0204,137 Multi-threading processors, integrated circuit devices, systems, and processes of operation and manufacture 43 2006
 
ENTERASYS NETWORKS, INC. (2)
5,528,513 Scheduling and admission control policy for a continuous media server 194 1993
5,898,694 Method of round robin bus arbitration 37 1996
 
INTELLECTUAL VENTURES I LLC (2)
5,793,993 Method for transmitting bus commands and data over two wires of a serial bus 72 1995
5,938,742 Method for configuring an intelligent low power serial bus 79 1995
 
NVIDIA CORPORATION (2)
7,015,913 Method and apparatus for multithreaded processing of data in a programmable graphics processor 70 2003
* 6,987,517 Programmable graphics processor for generalized texturing 19 2004
 
SAMSUNG ELECTRONICS CO., LTD. (2)
6,272,579 Microprocessor architecture capable of supporting multiple heterogeneous processors 80 1999
7,269,712 Thread selection for fetching instructions for pipeline multi-threaded processor 19 2004
 
ADVANCED MICRO DEVICES, INC. (1)
5,832,278 Cascaded round robin request selection method and apparatus 63 1997
 
ALCATEL USA SOURCING, L.P. (1)
6,434,155 Weighted round robin engine used in scheduling the distribution of ATM cells 38 1999
 
CISCO TECHNOLOGY, INC. (1)
7,441,101 Thread-aware instruction fetching in a multithreaded embedded processor 17 2004
 
Data General Corporation (1)
5,745,778 Apparatus and method for improved CPU affinity in a multiprocessor system 240 1994
 
EMC CORPORATION (1)
6,105,053 Operating system for a non-uniform memory access multiprocessor system 137 1995
 
FLOW WISE NETWORKS INC. (1)
6,163,827 Method and apparatus for round-robin flash channel arbitration 18 1997
 
FORCE 10 NETWORKS, INC. (1)
6,868,529 Method and apparatus for efficient implementation of round robin control unit 20 2001
 
FUJITSU LIMITED (1)
6,754,736 Information processing apparatus, data inputting/outputting method, and program storage medium therefor 24 2000
 
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
 
GLOBALFOUNDRIES INC. (1)
6,563,818 Weighted round robin cell architecture 54 1999
 
HTC CORPORATION (1)
6,549,930 Method for scheduling threads in a multithreaded processor 101 1997
 
LUCENT TECHNOLOGIES INC. (1)
7,007,153 Method and apparatus for allocating functional units in a multithreaded VLIW processor 21 2000
 
MARVELL WORLD TRADE LTD. (1)
2006/0212,853 Real-time control apparatus having a multi-thread processor 26 2005
 
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 108 1997
 
MICROVISION, INC. (1)
7,120,714 High-speed starvation-free arbiter system, rotating-priority arbiter, and two stage arbitration method 37 2003
 
MODULAR COMPUTER SYSTEMS, INC. A FLORIDA CORPORATION (1)
4,924,380 Dual rotating priority arbitration method for a multiprocessor memory bus 54 1988
 
NEC CORPORATION (1)
6,556,571 Fast round robin priority port scheduler for high capacity ATM switches 33 1999
 
NETLOGIC MICROSYSTEMS, INC. (1)
* 7,334,086 Advanced processor with system on a chip interconnect technology 43 2004
 
NOMADIX, INC. (1)
6,810,426 Methods and systems providing fair queuing and priority scheduling to enhance quality of service in a network 96 2002
 
NORTEL NETWORKS LIMITED (1)
6,470,016 Servicing output queues dynamically according to bandwidth allocation in a frame environment 90 1999
 
RENESAS ELECTRONICS AMERICA, INC. (1)
* 5,860,000 Floating point unit pipeline synchronized with processor pipeline 25 1996
 
ROCKWELL TECHNOLOGIES, LLC (1)
6,665,760 Group shifting and level shifting rotational arbiter system 33 2000
 
ROUND ROCK RESEARCH, LLC (1)
6,170,051 Apparatus and method for program level parallelism in a VLIW processor 141 1997
 
SONY COMPUTER ENTERTAINMENT INC. (1)
2006/0123,420 Scheduling method, scheduling apparatus and multiprocessor system 29 2005
 
STMICROELECTRONICS S.R.L. (1)
6,633,939 Variable-priority arbitration method and respective system 20 2001
 
SYNOPSYS, INC. (1)
7,051,189 Method and apparatus for processor code optimization using code compression 29 2001
 
THOMSON LICENSING (1)
2005/0076,189 Method and apparatus for pipeline processing a chain of processing instructions 18 2004
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
MIPS TECHNOLOGIES, INC. (2)
7,853,777 Instruction/skid buffers in a multithreading microprocessor that store dispatched instructions to avoid re-fetching flushed instructions 2 2005
8,151,268 Multithreading microprocessor with optimized thread scheduler for increasing pipeline utilization efficiency 0 2010
 
ARM FINANCE OVERSEAS LIMITED (1)
8,078,840 Thread instruction fetch based on prioritized selection from plural round-robin outputs for different thread states 1 2008
 
PANASONIC CORPORATION (1)
* 8,001,549 Multithreaded computer system and multithread execution control method 4 2007
* 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