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

ALSO PUBLISHED AS: 20060179284
ATTORNEY / AGENT: (SPONSORED)
 

Importance

Loading Importance Indicators... loading....

Abstract

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

Related Publications

Loading Related Publications... loading....

Patent Owner(s)

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

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Jensen, Michael Gottlieb Holte, DK 46 352
Jones, Darren M Los Altos, CA 30 285
Kinter, Ryan C Los Altos, CA 58 343
Vishin, Sanjay Sunnyvale, CA 38 695

Cited Art

Patent Info (Count) # Cites Year
 
BRIDGE CROSSING, LLC (11)
6,477,562 Prioritized instruction scheduling for multi-streaming processors 93 1998
6,389,449 Interstream control and communications for multi-streaming digital processors 100 1999
2002/0083,173 Method and apparatus for optimizing selection of available contexts for packet processing in multi-stream packet processing 54 2001
2006/0179,280 Multithreading processor including thread scheduler based on instruction stall likelihood prediction 31 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 12 2005
2008/0069,115 BIFURCATED TRANSACTION SELECTOR SUPPORTING DYNAMIC PRIORITIES IN MULTI-PORT SWITCH 17 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 17 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 25 2007
 
INTEL CORPORATION (9)
5,357,512 Conditional carry scheduler for round robin scheduling 24 1992
6,658,447 Priority based simultaneous multi-threading 71 1997
6,272,520 Method for detecting thread switch events 82 1997
6,542,921 Method and apparatus for controlling the processing priority between multiple threads in a multithreaded processor 54 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 57 2001
6,792,446 Storing of instructions relating to a stalled thread 27 2002
2003/0233,394 Method and apparatus for ensuring fairness and forward progress when executing multiple threads of execution 26 2002
2004/0128,448 Apparatus for memory communication during runahead execution 25 2002
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (7)
5,067,069 Control of multiple functional units with parallel operation in a microcoded execution unit 81 1989
5,095,460 Rotating priority encoder operating by selectively masking input signals to a fixed priority encoder 26 1989
6,073,159 Thread properties attribute vector based thread selection in multithreading processor 60 1996
6,032,218 Configurable weighted round robin arbiter 55 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 16 2001
2006/0168,254 Automatic policy selection 21 2004
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (6)
6,105,051 Apparatus and method to guarantee forward progress in execution of threads in a multithreaded processor 61 1997
6,567,839 Thread switch control in a multithreaded processor system 165 1997
6,237,081 Queuing method and apparatus for facilitating the rejection of sequential instructions in a processor 17 1998
6,516,369 Fair and high speed arbitration system based on rotative and weighted priority monitoring 35 1999
7,096,470 Method and apparatus for implementing thread replacement for optimal performance in a two-tiered multithreading structure 19 2002
2006/0168,393 Apparatus and method for dependency tracking and register file bypass controls using a scannable register file 16 2005
 
SUN MICROSYSTEMS, INC. (5)
5,546,554 Apparatus for dynamic register management in a floating point unit 58 1994
6,094,435 System and method for a quality of service in a multi-layer network element 163 1997
6,295,600 Thread switch on blocked load or store using instruction thread field 68 1999
7,185,178 Fetch speculation in a multithreaded processor 33 2004
2006/0004,989 Mechanism for selecting instructions for execution in a multithreaded processor 24 2004
 
GOOGLE INC. (4)
6,076,157 Method and apparatus to force a thread switch in a multithreaded processor 145 1997
6,212,544 Altering thread priorities in a multithreaded processor 200 1997
6,694,425 Selective flush of shared and other pipeline stages in a multithread processor 56 2000
6,721,874 Method and system for dynamically shared completion table supporting multiple threads in a processing system 27 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 30 1996
2006/0179,274 Instruction/skid buffers in a multithreading microprocessor 24 2005
2006/0179,279 Bifurcated thread scheduler in a multithreading microprocessor 23 2005
 
KABUSHIKI KAISHA TOSHIBA (3)
6,101,193 Packet scheduling scheme for improving short time fairness characteristic in weighted fair queueing 87 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 22 2004
 
TEXAS INSTRUMENTS INCORPORATED (3)
5,913,049 Multi-stream complex instruction set microprocessor 73 1997
2006/0095,732 Processes, circuits, devices, and systems for scoreboard and other processor improvements 45 2005
2007/0204,137 Multi-threading processors, integrated circuit devices, systems, and processes of operation and manufacture 36 2006
 
ENTERASYS NETWORKS, INC. (2)
5,528,513 Scheduling and admission control policy for a continuous media server 176 1993
5,898,694 Method of round robin bus arbitration 36 1996
 
NVIDIA CORPORATION (2)
7,015,913 Method and apparatus for multithreaded processing of data in a programmable graphics processor 57 2003
6,987,517 Programmable graphics processor for generalized texturing 17 2004
 
SAMSUNG ELECTRONICS CO., LTD. (2)
6,272,579 Microprocessor architecture capable of supporting multiple heterogeneous processors 71 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 57 1997
 
ALCATEL USA SOURCING, L.P. (1)
6,434,155 Weighted round robin engine used in scheduling the distribution of ATM cells 30 1999
 
BEN FRANKLIN PATENT HOLDING LLC (1)
5,793,993 Method for transmitting bus commands and data over two wires of a serial bus 57 1995
 
CISCO TECHNOLOGY, INC. (1)
7,441,101 Thread-aware instruction fetching in a multithreaded embedded processor 14 2004
 
DATA GENERAL CORPORATION (1)
5,745,778 Apparatus and method for improved CPU affinity in a multiprocessor system 193 1994
 
EMC CORPORATION (1)
6,105,053 Operating system for a non-uniform memory access multiprocessor system 120 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 23 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 39 1991
 
GLOBALFOUNDRIES INC. (1)
6,563,818 Weighted round robin cell architecture 49 1999
 
HTC CORPORATION (1)
6,549,930 Method for scheduling threads in a multithreaded processor 87 1997
 
INTELLECTUAL VENTURES I LLC (1)
5,938,742 Method for configuring an intelligent low power serial bus 34 1995
 
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 15 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 99 1997
 
MICROVISION, INC. (1)
7,120,714 High-speed starvation-free arbiter system, rotating-priority arbiter, and two stage arbitration method 33 2003
 
MODULAR COMPUTER SYSTEMS, INC. A FLORIDA CORPORATION (1)
4,924,380 Dual rotating priority arbitration method for a multiprocessor memory bus 52 1988
 
NEC CORPORATION (1)
6,556,571 Fast round robin priority port scheduler for high capacity ATM switches 31 1999
 
NETLOGIC MICROSYSTEMS, INC. (1)
7,334,086 Advanced processor with system on a chip interconnect technology 32 2004
 
NOMADIX, INC. (1)
6,810,426 Methods and systems providing fair queuing and priority scheduling to enhance quality of service in a network 78 2002
 
NORTEL NETWORKS LIMITED (1)
6,470,016 Servicing output queues dynamically according to bandwidth allocation in a frame environment 74 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 30 2000
 
ROUND ROCK RESEARCH, LLC (1)
6,170,051 Apparatus and method for program level parallelism in a VLIW processor 121 1997
 
SONY COMPUTER ENTERTAINMENT INC. (1)
2006/0123,420 Scheduling method, scheduling apparatus and multiprocessor system 23 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 27 2001
 
THOMSON LICENSING (1)
2005/0076,189 Method and apparatus for pipeline processing a chain of processing instructions 18 2004

Patent Citation Ranking

Forward Cites

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
 
BRIDGE CROSSING, LLC (1)
8,078,840 Thread instruction fetch based on prioritized selection from plural round-robin outputs for different thread states 0 2008
 
PANASONIC CORPORATION (1)
8,001,549 Multithreaded computer system and multithread execution control method 1 2007

Maintenance Fees

Fee Large entity fee small entity fee micro entity fee due date
3.5 Year Payment $1600.00 $800.00 $400.00 Aug 2, 2013
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 - 3.5 year - Late payment within 6 months $160.00 $80.00 $40.00
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