Welcome Stranger to OCC!Login | Register

Easing Multicore Traffic Jams with Data Structures

Category: Science & Technology
Posted: 07:18AM

The saying goes that two heads are better than one, and in this case, what is true for humans is also true for processing cores, with multicore processors being more efficient than single core CPUs, to a point. That point comes when you are dealing with more than eight cores, because then the actions of the cores start running into each other. Researchers at MIT, however, have refined a data structure system to remove this problem until you reach 80 cores.

There are a variety of data structures that can be used, and each has their own advantages and disadvantages. A priority queue gives each piece of data a priority value when it is stored, and only those with the highest priority can be retrieved. With a multicore processor, each core is going to grab that data and put it in their cache, and then when one of them writes to the cache, it invalidates the caches of the other cores. To get around this, the researchers allow the cores to pull items other than the first in the queue, but then the cores have to know where to find the data.

One way to find the data is to build a link list, where each element points to the address of the next. This could lead to a similar traffic jam as before though, so the researchers instead employed a skip list, which uses multiple, smaller, linked lists. The cores are able to search these smaller lists first, to find the data, and if they do not, go down a layer to another linked list until they do find the data. This will not prevent the cores from running into each other, causing a traffic jam, but it will make it much less common.

Source: MIT

Register as a member to subscribe comments.

This news has comment postings disabled because it is now archived.

© 2001-2018 Overclockers Club ® Privacy Policy
Elapsed: 0.0293490887   (xlweb1)