Multithreading microprocessor with optimized thread scheduler for increasing pipeline utilization efficiency

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 7657891
APP PUB NO 20060179284A1
SERIAL NO

11051979

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
IMAGINATION TECHNOLOGIES, LLCKINGS LANGLEY, GB19

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Jensen, Michael Gottlieb Sunnyvale, US 26 501
Jones, Darren M Los Altos, US 17 428
Kinter, Ryan C Sammamish, US 34 521
Vishin, Sanjay Sunnyvale, US 26 845

Cited Art Landscape

Patent Info (Count) # Cites Year
 
SONY COMPUTER ENTERTAINMENT INC. (1)
2006/0123,420 Scheduling method, scheduling apparatus and multiprocessor system 36 2005
 
HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP (3)
6073159 Thread properties attribute vector based thread selection in multithreading processor 64 1996
6032218 Configurable weighted round robin arbiter 69 1998
6647449 System, method and circuit for performing round robin arbitration 41 2000
 
DATA GENERAL CORPORATION (1)
5745778 Apparatus and method for improved CPU affinity in a multiprocessor system 282 1994
 
SAMSUNG ELECTRONICS CO., LTD. (2)
6272579 Microprocessor architecture capable of supporting multiple heterogeneous processors 87 1999
7269712 Thread selection for fetching instructions for pipeline multi-threaded processor 19 2004
 
ORACLE AMERICA, INC. (1)
7185178 Fetch speculation in a multithreaded processor 54 2004
 
NEC CORPORATION (1)
6556571 Fast round robin priority port scheduler for high capacity ATM switches 34 1999
 
INTELLECTUAL VENTURES I LLC (2)
5793993 Method for transmitting bus commands and data over two wires of a serial bus 92 1995
5938742 Method for configuring an intelligent low power serial bus 130 1995
 
RENESAS ELECTRONICS AMERICA, INC. (1)
* 5860000 Floating point unit pipeline synchronized with processor pipeline 26 1996
 
KABUSHIKI KAISHA TOSHIBA (3)
6101193 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 34 2004
 
SYNOPSYS, INC. (1)
7051189 Method and apparatus for processor code optimization using code compression 31 2001
 
GOOGLE INC. (4)
6076157 Method and apparatus to force a thread switch in a multithreaded processor 189 1997
6212544 Altering thread priorities in a multithreaded processor 258 1997
* 6694425 Selective flush of shared and other pipeline stages in a multithread processor 70 2000
6721874 Method and system for dynamically shared completion table supporting multiple threads in a processing system 30 2000
 
MARVELL WORLD TRADE LTD. (1)
2006/0212,853 Real-time control apparatus having a multi-thread processor 65 2005
 
ALCATEL USA SOURCING, L.P. (1)
6434155 Weighted round robin engine used in scheduling the distribution of ATM cells 41 1999
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (1)
* 7334086 Advanced processor with system on a chip interconnect technology 56 2004
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (6)
6105051 Apparatus and method to guarantee forward progress in execution of threads in a multithreaded processor 69 1997
6567839 Thread switch control in a multithreaded processor system 201 1997
6237081 Queuing method and apparatus for facilitating the rejection of sequential instructions in a processor 19 1998
6516369 Fair and high speed arbitration system based on rotative and weighted priority monitoring 37 1999
* 7096470 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 18 2005
 
ADVANCED MICRO DEVICES, INC. (1)
5832278 Cascaded round robin request selection method and apparatus 63 1997
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (4)
* 5067069 Control of multiple functional units with parallel operation in a microcoded execution unit 84 1989
5095460 Rotating priority encoder operating by selectively masking input signals to a fixed priority encoder 27 1989
6918116 Method and apparatus for reconfiguring thread scheduling using a thread scheduler function unit 19 2001
2006/0168,254 Automatic policy selection 31 2004
 
LUCENT TECHNOLOGIES INC. (1)
7007153 Method and apparatus for allocating functional units in a multithreaded VLIW processor 22 2000
 
EXTREME NETWORKS, INC. (1)
5898694 Method of round robin bus arbitration 37 1996
 
CISCO TECHNOLOGY, INC. (1)
7441101 Thread-aware instruction fetching in a multithreaded embedded processor 21 2004
 
ENTERASYS NETWORKS, INC. (1)
5528513 Scheduling and admission control policy for a continuous media server 220 1993
 
GLOBALFOUNDRIES INC. (1)
6563818 Weighted round robin cell architecture 56 1999
 
THOMSON LICENSING (1)
2005/0076,189 Method and apparatus for pipeline processing a chain of processing instructions 19 2004
 
ROCKWELL TECHNOLOGIES, LLC (1)
6665760 Group shifting and level shifting rotational arbiter system 35 2000
 
Modular Computer Systems, Inc. (1)
4924380 Dual rotating priority arbitration method for a multiprocessor memory bus 54 1988
 
FUJITSU LIMITED (1)
6754736 Information processing apparatus, data inputting/outputting method, and program storage medium therefor 24 2000
 
SUN MICROSYSTEMS, INC. (4)
* 5546554 Apparatus for dynamic register management in a floating point unit 74 1994
6094435 System and method for a quality of service in a multi-layer network element 182 1997
6295600 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 29 2004
 
GATEWAY, INC. (1)
5276887 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)
6170051 Apparatus and method for program level parallelism in a VLIW processor 148 1997
 
FORCE 10 NETWORKS, INC. (1)
6868529 Method and apparatus for efficient implementation of round robin control unit 22 2001
 
EMC CORPORATION (1)
6105053 Operating system for a non-uniform memory access multiprocessor system 155 1995
 
INTEL CORPORATION (9)
5357512 Conditional carry scheduler for round robin scheduling 29 1992
6658447 Priority based simultaneous multi-threading 115 1997
6272520 Method for detecting thread switch events 99 1997
6542921 Method and apparatus for controlling the processing priority between multiple threads in a multithreaded processor 65 1999
6609190 Microprocessor with primary and secondary issue queue 24 2000
6385715 Multi-threading for a processor utilizing a replay queue 72 2001
6792446 Storing of instructions relating to a stalled thread 31 2002
2003/0233,394 Method and apparatus for ensuring fairness and forward progress when executing multiple threads of execution 49 2002
2004/0128,448 Apparatus for memory communication during runahead execution 43 2002
 
MIPS TECHNOLOGIES, INC. (4)
5309382 Binary shifter 27 1992
5734877 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 25 2005
2006/0179,279 Bifurcated thread scheduler in a multithreading microprocessor 29 2005
 
HTC CORPORATION (1)
6549930 Method for scheduling threads in a multithreaded processor 115 1997
 
STMICROELECTRONICS S.R.L. (1)
6633939 Variable-priority arbitration method and respective system 20 2001
 
MICROVISION, INC. (1)
7120714 High-speed starvation-free arbiter system, rotating-priority arbiter, and two stage arbitration method 39 2003
 
TEXAS INSTRUMENTS INCORPORATED (3)
5913049 Multi-stream complex instruction set microprocessor 81 1997
2006/0095,732 Processes, circuits, devices, and systems for scoreboard and other processor improvements 62 2005
2007/0204,137 Multi-threading processors, integrated circuit devices, systems, and processes of operation and manufacture 58 2006
 
FLOW WISE NETWORKS INC. (1)
6163827 Method and apparatus for round-robin flash channel arbitration 18 1997
 
NVIDIA CORPORATION (2)
7015913 Method and apparatus for multithreaded processing of data in a programmable graphics processor 83 2003
* 6987517 Programmable graphics processor for generalized texturing 20 2004
 
ARM FINANCE OVERSEAS LIMITED (11)
6477562 Prioritized instruction scheduling for multi-streaming processors 109 1998
6389449 Interstream control and communications for multi-streaming digital processors 109 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
* 7490230 Fetch director employing barrel-incrementer-based round-robin apparatus for use in multithreading microprocessor 16 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)
6810426 Methods and systems providing fair queuing and priority scheduling to enhance quality of service in a network 116 2002
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
6105127 Multithreaded processor for processing multiple instruction streams independently of each other by flexibly controlling throughput in each instruction stream 116 1997
 
NORTEL NETWORKS LIMITED (1)
6470016 Servicing output queues dynamically according to bandwidth allocation in a frame environment 107 1999
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
SOCIONEXT INC. (2)
* 8001549 Multithreaded computer system and multithread execution control method 5 2007
* 2007/0266,387 MULTITHREADED COMPUTER SYSTEM AND MULTITHREAD EXECUTION CONTROL METHOD 12 2007
 
APPSENSE LIMITED (1)
9542235 Process-safe read/write locks 0 2010
 
MIPS TECHNOLOGIES, INC. (2)
7853777 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 25 2005
 
ARM FINANCE OVERSEAS LIMITED (4)
8078840 Thread instruction fetch based on prioritized selection from plural round-robin outputs for different thread states 9 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 7 2009
 
IMAGINATION TECHNOLOGIES, LLC (1)
8151268 Multithreading microprocessor with optimized thread scheduler for increasing pipeline utilization efficiency 1 2010
* 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