editor's blog
Subscribe Now

Making the Line Move Faster

No one likes standing in line, but if you’re going to be doing any serious parallel processing, you’ll run into many queues as a way for threads or processes to send messages to each other. Usually they’re implemented in software, which adds a level of overhead to the programs, in particular when putting things on or taking them off the queue.

For instance, when putting a new item into the queue, you have to check to see if there is room in the queue, and you have to upgrade the head afterwards, and, by the time all is said and done, you’ve chewed up 10 instructions. In addition, the queue information may or may not be in the cache, and you have to ensure exclusive access where critical, and, well, it can get slow enough to where you want to limit how many things work in parallel and how much they communicate. If the program is split up too finely, then too much time is lost to the not-so-instant messaging between processes or threads

In order to alleviate this, hardware queues have been proposed. But these interrupt the micro-architecture and require custom interconnect. Worse yet, they’re not well handled by operating systems, especially when it comes to context switches. And architects have the unenviable job of deciding how big to make them and how many to provide: you know they’ll never get that right in everyone’s eyes.

In one of those random encounters of something interesting, I ran across a recent report by Lee et al from the University of North Carolina that takes a middle road for single-producer/single-consumer queues: hardware-accelerated software queues. In so doing, there were four primary criteria they wanted to meet:

  1. The frequent enqueue and dequeue tasks have to be as efficient as possible. Hardware queues meet this; software queues don’t.
  2. The time between one entity putting something on the queue and something else taking it off should be as short as possible. Again, hardware queues can do this; software queues, not so much.
  3. They should be as easy to program as software queues (quantity, synchronization, etc.). Software queues meet this by definition; hardware queues don’t at the very least by virtue of their limited quantity and size.
  4. They have to work without changing the OS. Because software queues work in the application memory space, they can do this; hardware queues can’t.

The abridged version of what they do can be summarized by four primary points:

  • While still implementing the queue in memory, cache a local copy of the queue head, tail, and size in a separate dedicated hardware table. This table stores some number of active queues much the way a memory cache stores some number of active memory addresses. This means that the various bookkeeping steps can be done without going to memory and without contention from anyone else.
  • Pipeline the queue operations into three steps: address generation, the actual store or load, and index updating.
  • Use dedicated hardware to calculate the address of the store or load. Again, this happens in private hardware without interference; multiple addresses can be generated in a single operation. The actual load or store can happen when the address is ready, meaning that the queue operations may happen out of order (if an early one takes longer to have its address resolved, for instance).
  • Accumulate index updates and store a bunch of them at the same time to reduce the amount of access to the cache.

Of course, as with everything, the details hide much devilry, so they have special considerations to handle misspeculation, precise interrupts, a full queue cache, fence (memory barrier) instructions, and avoiding livelock (since, in theory, the various queue indices could reside on three different memory pages that an OS may not be able to keep in memory at the same time).

With this solution, Criterion 1 is met because of the hardware acceleration, as is Criterion 2. Because the actual queues are still implemented in the application memory space, with no specific size or quantity limits, Criteria 3 and 4 are met.

For details on all of this as well as the results of their testing, you can check out the paper courtesy of James Tuck, one of the authors.

Leave a Reply

featured blogs
Nov 30, 2022
By Joe Davis Sponsored by France's ElectroniqueS magazine, the Electrons d'Or Award program identifies the most innovative products of the… ...
Nov 29, 2022
Smart manufacturing '“ the use of nascent technology within the industrial Internet of things (IIoT) to address traditional manufacturing challenges '“ is leading a supply chain revolution, resulting in smart, connected, and intelligent environments, capable of self-operati...
Nov 22, 2022
Learn how analog and mixed-signal (AMS) verification technology, which we developed as part of DARPA's POSH and ERI programs, emulates analog designs. The post What's Driving the World's First Analog and Mixed-Signal Emulation Technology? appeared first on From Silicon To So...
Nov 18, 2022
This bodacious beauty is better equipped than my car, with 360-degree collision avoidance sensors, party lights, and a backup camera, to name but a few....

featured video

How to Harness the Massive Amounts of Design Data Generated with Every Project

Sponsored by Cadence Design Systems

Long gone are the days where engineers imported text-based reports into spreadsheets and sorted the columns to extract useful information. Introducing the Cadence Joint Enterprise Data and AI (JedAI) platform created from the ground up for EDA data such as waveforms, workflows, RTL netlists, and more. Using Cadence JedAI, engineering teams can visualize the data and trends and implement practical design strategies across the entire SoC design for improved productivity and quality of results.

Learn More

featured paper

Algorithm Verification with FPGAs and ASICs

Sponsored by MathWorks

Developing new FPGA and ASIC designs involves implementing new algorithms, which presents challenges for verification for algorithm developers, hardware designers, and verification engineers. This eBook explores different aspects of hardware design verification and how you can use MATLAB and Simulink to reduce development effort and improve the quality of end products.

Click here to read more

featured chalk talk

Quick Connect IoT

Sponsored by Mouser Electronics and Renesas

Rapid prototyping is a vital first element to get your next IoT design into the real world. In this episode of Chalk Talk, Brad Rex from Renesas and Amelia Dalton examine Renesas’ new Quick Connect IoT out of the box IoT solution that combines well-defined API and middleware with certified module solutions to make rapid prototyping faster and easier than ever before. They also investigate how the Quick Connect IoT integrated software can help MCUs, sensors and connectivity devices communicate effectively and how you can get started using Quick-Connect IoT for your next IoT design.

Click here for more information about Renesas Electronics Quick Connect IoT