Mémoire tampon | EPFL Graph Search

thumb|Un buffer Intel sur une barrette de mémoire vive. En informatique, une mémoire tampon, couramment désignée par le terme anglais buffer, est une zone de mémoire vive ou de disque utilisée pour entreposer temporairement des données, notamment entre deux processus ou matériels ne travaillant pas au même rythme. Description Du fait de la différence de vitesse entre le processeur et le périphérique, les données envoyées vers un périphérique (interne ou externe) sont le plus souvent stockées dans des mémoires tampon en attente de leur envoi effectif vers le périphérique, pour épargner à l’ordinateur l'attente due à la différence de débits entre le microprocesseur interne et les différents périphériques souvent lents. De même, les données reçues de l'extérieur sont le plus souvent rassemblées dans des tampons, en attente de leur traitement par l'ordinateur (pour des raisons d'efficacité, et aussi pour éviter qu'une réception de données trop rapprochées fasse que certaines, n

Buffer Placement and Sizing for High-Performance Dataflow Circuits

Andrea Guerrieri, Paolo Ienne, Lana Josipovic, Shabnam Sheikhha

Commercial high-level synthesis tools typically produce statically scheduled circuits. Yet, effective C-to-circuit conversion of arbitrary software applications calls for dataflow circuits, as they can handle efficiently variable latencies (e.g., caches) and unpredictable memory dependencies. Dataflow circuits exhibit an unconventional property: registers (usually referred to as "buffers") can be placed anywhere in the circuit without changing its semantics, in strong contrast to what happens in traditional datapaths. Yet, although functionally irrelevant, this placement has a significant impact on the circuit's timing and throughput. In this work, we show how to strategically place buffers into a dataflow circuit to optimize its performance. Our approach extracts a set of choice-free critical loops from arbitrary dataflow circuits and relies on the theory of marked graphs to optimize the buffer placement and sizing. We demonstrate the performance benefits of our approach on a set of dataflow circuits obtained from imperative code.

ASSOC COMPUTING MACHINERY2020

Quality of Service Provided by Deficit Round Robin Algorithm

Nevena Krsmanovic, Nevena Vratonjic

In this paper we examine performance of the switches with output buffers for traffic with reservations and best-effort traffic. Packets are scheduled according to the Deficit Round Robin (DRR) algorithm. The DRR has been modeled, and quality of service in terms of delay and fairness provided by this architecture has been analyzed. Our results confirm that DRR provide both delay guarantees and a fair service

2006

High-Level Synthesis of Dynamically Scheduled Circuits

Lana Josipovic

High-Level Synthesis (HLS) tools generate hardware designs from high-level programming languages. These tools almost universally build datapaths that are controlled using a centralized controller which relies on a static, compile-time schedule to determine the cycle when each operation executes. Such an approach results in high-throughput pipelines in cases where memory accesses are provably independent and critical control decisions are determinable during code compilation. Unfortunately, when this is not the case, the tools must make pessimistic assumptions, yielding inferior schedules and lower performance. An alternative HLS approach is to create dataflow circuits out of high-level code. Dataflow circuits are built out of units which communicate using point-to-point pairs of handshake control signals; data is propagated from unit to unit as soon as memory and control dependences allow it and stalled by the handshaking mechanism otherwise. This distributed control mechanism effectively implements a dynamic schedule, where scheduling decisions are made locally in the circuit as it runs, hence achieving behaviors which are beyond the capabilities of statically scheduled circuits. Although translating high-level code into dataflow circuits seems relatively straightforward, a naive translation is not sufficient to achieve functional correctness, high performance, and area efficiency. Firstly, without appropriate buffer placement and sizing, dataflow circuits exhibit only limited pipelining capabilities. Secondly, in the absence of a static schedule, resource sharing opportunities are difficult to identify; in addition, sharing may cause deadlock and compromise the functionality of the circuit. Thirdly, memory accesses in a dataflow circuit may execute in an order different than the one specified in the original program---a naive memory interface is not always sufficient to guarantee that all memory dependences are honored. Finally, standard dataflow circuits do not support speculation, i.e., the ability to execute some operations before it is certain whether they are correct or required, which prevents pipelining when a memory or a control dependence takes a long time to resolve. The contribution of this thesis is to develop techniques that make dataflow circuits truly competitive in the HLS context. We first present a complete set of rules and transformations to create dataflow circuits out of high-level specifications (i.e., C/C++ programs). We detail a methodology to systematically place and size buffers in dataflow circuits to achieve high-throughput pipelines. We show how to automatically identify performance-acceptable resource sharing opportunities and describe a sharing mechanism which achieves functionally correct and deadlock-free dataflow designs. We detail the construction of a memory interface (i.e., a load-store queue) for dataflow circuits that can correctly handle memory accesses arriving out of order and show how to automatically customize this interface to a particular application. Further, we present a generic framework for handling speculation in dataflow circuits. Finally, we show that these techniques can reap significant area/performance benefits in appropriate situations. All these features enable dataflow circuits to achieve dynamic behaviors similar to those of modern superscalar processors; we believe that these behaviors are key for HLS to be successful in new contexts and broader application domains.

EPFL2021

High-Level Synthesis of Dynamically Scheduled Circuits

Lana Josipovic

EPFL2021