Sign in with
Sign up | Sign in

Intel Patents Thread Scheduling

By - Source: USPTO | B 31 comments

Intel has been awarded a patent that provides basic information about the company's thread scheduling approach in multi-processor computers. Filed on March 26, 2007 the USPTO confirmed the rights to it earlier this week.

The patent include the idea to leverage stored instructions in a computer system to "assign two threads to processors based on bandwidth utilization of the two threads in combination; determine whether the bandwidth utilization of the two combined threads exceeds a threshold value; use a cache simulator to construct a coupling degree matrix; use a software library to develop said coupling degree matrix; and use the coupling degree matrix to allocate threads to processors when the bandwidth utilization does not exceed said threshold."

Also claimed are instructions that provide information on whether the bandwidth utilization exceeds a threshold of 15 percent, as well as a capability to store "the coupling degree matrix by rating two threads in terms of the total amount of accesses to cache lines shared between two threads," as well as a "scheduler to determine the coupling degree matrix by rating the threads in terms of the total amount of accesses to cache lines."


In the scheduling process, idle threads and idle process pairs are first identified and a loop to check for more pairs is launched, after which threads to idle processors are assigned. This process repeats until all process pairs have been covered. As soon as no more pairs are available, the loop may identify an individual thread that is assigned to a process.

The patented scheduler uses information about the location of data between threads and bandwidth demand to evaluate thread allocation for performance purposes. According to the patent, bandwidth utilization is considered the highest priority in determining the thread schedule, followed by data location. The document concludes that, if a bandwidth threshold of co-scheduled threads on one cluster exceeds a certain level, "for example 15 percent", the system would schedule the threads on different clusters. If the utilization is below the defined level, the system assumes that closely coupled threads on one cluster would achieve higher performance.

Display 31 Comments.
This thread is closed for comments
Top Comments
  • 16 Hide
    TheFoxyBox , March 11, 2012 5:01 AM
    jackt?Then we wonder why a quad core is not 4 times powerfull than a smame clock single core.


    Because cores don't scale perfectly? Plus you also have to factor in the software you're using, cache, architecture, pipelining, 32- or 64-bit etc.
  • 16 Hide
    crisan_tiberiu , March 11, 2012 9:24 AM
    this patent system its kinda lame imo..
  • 15 Hide
    bison88 , March 11, 2012 4:25 AM
    kensingtronDid anyone else find the details of this article flew over their head?


    As do most things when it's in regards to patents. You practically need a doctorate to read 'em and a lawyer to write them.
Other Comments
  • 14 Hide
    buzznut , March 11, 2012 3:18 AM
    This sounds like decidedly bad news for AMD.
  • 8 Hide
    killabanks , March 11, 2012 3:40 AM
    sounds like maybe a patent for hyperthreading?
  • 7 Hide
    jprahman , March 11, 2012 4:04 AM
    killabankssounds like maybe a patent for hyperthreading?

    It certainly does, at least as an improvement to it. A major disadvantage of Hyper-threading in the P4 was that two threads running on the same processor could interfere with each others cache lines. It is possible that the reason behind the reintroduction of Hyper-threading in the Nehalem architecture was that Intel was able to implement this technology, or something similar, and as a result was able to achieve a larger performance gain from Hyper-threading.
  • 15 Hide
    bison88 , March 11, 2012 4:25 AM
    kensingtronDid anyone else find the details of this article flew over their head?


    As do most things when it's in regards to patents. You practically need a doctorate to read 'em and a lawyer to write them.
  • 16 Hide
    TheFoxyBox , March 11, 2012 5:01 AM
    jackt?Then we wonder why a quad core is not 4 times powerfull than a smame clock single core.


    Because cores don't scale perfectly? Plus you also have to factor in the software you're using, cache, architecture, pipelining, 32- or 64-bit etc.
  • -5 Hide
    memadmax , March 11, 2012 5:23 AM
    Idle hands are the devils tools....
  • 15 Hide
    mrkdilkington , March 11, 2012 5:36 AM
    I wasn't aware you could patent an algorithm.
  • 2 Hide
    JOSHSKORN , March 11, 2012 6:42 AM
    Sounds like AMD just got...bulldozed.
  • 14 Hide
    theuniquegamer , March 11, 2012 7:43 AM
    Patent every thing you discover ASAP Before apple knows it and gets it patented .
  • 16 Hide
    crisan_tiberiu , March 11, 2012 9:24 AM
    this patent system its kinda lame imo..
  • 10 Hide
    master9716 , March 11, 2012 12:37 PM
    This is like saying im going to Patent how many people go into and come out of the super market at the same time. Something has to be done about the patent system !!!!!!!!
  • -5 Hide
    acerace , March 11, 2012 1:03 PM
    Quote:
    Sounds like AMD just got...bulldozed.


    Yyyeaaaahhhhh~.
  • 3 Hide
    cookoy , March 11, 2012 1:13 PM
    Between the time of the filing and the time the patent got approved (let's just say April 2007 to Feb 2012), if AMD came out with something similar in their cpu design, did AMD violate Intel's patent? Like a crime is breaking the law and if there is no law then there is no crime. You can't apply the law retroactively. Any legal experts out there to enlighten us on this?
  • -5 Hide
    dealcorn , March 11, 2012 1:41 PM
    I suspect Intel's filing was motivated by an interest in defense. They prefer not to be extorted and games rules require this. As to AMD, get real: why bother. Intel is achieving what they want in the marketplace. Conduct which might draw a foul is neither helpful nor required.
  • 3 Hide
    fazers_on_stun , March 11, 2012 2:11 PM
    cookoyBetween the time of the filing and the time the patent got approved (let's just say April 2007 to Feb 2012), if AMD came out with something similar in their cpu design, did AMD violate Intel's patent? Like a crime is breaking the law and if there is no law then there is no crime. You can't apply the law retroactively. Any legal experts out there to enlighten us on this?


    Under current US patent law, priority is awarded to the 'first to invent' something. So in order for AMD to prevail under your scenario above, they would have to demonstrate that they conceived and reduced to practice the claimed invention before Intel did. To show prior conception, they would have to have lab notes and other written evidence predating Intel's, showing that they thought of the idea before Intel did.

    Usually the first to file a patent application on the idea is taken as constructive reduction to practice. However if AMD could show they were diligently (i.e., no long breaks) working on the invention, they could supercede Intel in what is called an interference proceeding and be awarded priority.

    However under the American Inventor's Act, which goes into full effect this year IIRC, US patent law is being harmonized with European and Japanese patent law, which awards priority to the first to file a patent application. So that means if you file an application first, you are automatically awarded priority no matter how much work the competition can show they did before you filed, or did for that matter.

    However I also think that AMD & Intel have a cross-licensing agreement in effect which may mean that AMD gets to use Intel's patents in exchange for the X64 patent that belongs to AMD. Not sure of the particulars of that agreement, so I dunno if it covers new stuff like this. But, if true, then this patent would deter somebody like ARM if they wanna get into hyperthreading and use the same or not-patentably-distinct (obvious) variation on Intel's patented technology, whereas AMD would not have to worry about it.
  • 4 Hide
    scook9 , March 11, 2012 2:26 PM
    mrkdilkingtonI wasn't aware you could patent an algorithm.

    Actually an algorithm is exactly the kind of thing that SHOULD be patented. It takes a lot of critical thinking and design to come up with a solid algorithm. It is not a given like a law of physics, it is absolutely intellectual property.

    In my opinion, this is exactly the kind of thing that SHOULD be patented. Not UI design bullshit, but actual technology. What is more, you can probably bet that Intel will not use this as a sword against competition, it is not how they role.
  • 2 Hide
    freggo , March 11, 2012 3:52 PM
    scook9Actually an algorithm is exactly the kind of thing that SHOULD be patented. It takes a lot of critical thinking and design to come up with a solid algorithm. It is not a given like a law of physics, it is absolutely intellectual property.In my opinion, this is exactly the kind of thing that SHOULD be patented. Not UI design bullshit, but actual technology. What is more, you can probably bet that Intel will not use this as a sword against competition, it is not how they role.


    As a former game coder I disagree.
    A good algorithm is simply providing the most effective or logical solution for a given situation.
    As such it is not a "law of physics" but a "law of logic" than one patents.

    This should not be confused with the algorithm for say the AI of a game. That's not necessarily dictated by outright logic of course.


  • -3 Hide
    bloc97 , March 11, 2012 4:07 PM
    All those process won't eat CPU cycles? Maby the algorithm was made to accelerate the CPU, but itself may slow down the CPU, so at the end, the performance is the same until we ameliorate the code.

    It always begin like this...
  • 2 Hide
    jamie_1318 , March 11, 2012 5:26 PM
    bloc97All those process won't eat CPU cycles? Maby the algorithm was made to accelerate the CPU, but itself may slow down the CPU, so at the end, the performance is the same until we ameliorate the code.It always begin like this...


    You are looking at one cycle in billions. Literally. if it checks only a few times a second a core nearing it's threshold and splitting threads onto other cores, the extra power savings (intelligently disabling other cores) and performance gains (never having to worry about wasting user time) is is a superfluous concern.

    Not only that but they can run these checks using some part of uncore, and not have any hit at all and enabling a much faster update frequency.
Display more comments