Arthur Perais
email: arthur.perais@inria.fr

André Seznec
email: andre.seznec@inria.fr

Cost Effective Physical Register Sharing 1

Sharing a physical register between several instructions is needed to implement several microarchitectural optimizations. However, register sharing requires modifications to the register reclaiming process: Committing a single instruction does not guarantee that the physical register allocated to the previous mapping of its architectural destination register is freeable anymore. Consequently, a form of register reference counting must be implemented.

While such mechanisms (e.g., dependency matrix, per register counters) have been described in the literature, we argue that they either require too much storage, or that they lengthen branch misprediction recovery by requiring sequential rollback. As an alternative, we present the Inflight Shared Register Buffer (ISRB), a new structure for register reference counting. The ISRB has low storage overhead and lends itself to checkpoint-based recovery schemes, therefore allowing fast recovery on pipeline flushes.

We illustrate our scheme with Move Elimination (shortcircuiting moves) and an implementation of Speculative Memory Bypassing (short-circuiting store-load pairs) that makes use of a TAGE-like predictor to identify memory dependencies. We show that the whole potential of these two mechanisms can be achieved with a small register tracking structure.

INTRODUCTION & BACKGROUND

As most general purpose instructions are destructive in x86 (i.e., one of the source gets overwritten by the result), registerto-register moves are widely used. Those moves consume processor resources and execution bandwidth but would be unnecessary if instructions had distinct destination registers.

In particular, the limited number of architectural registers often forces the compiler to spill variables to memory, only to reload them a few cycles later. Communicating values through memory is slower, since a load-to-use delay is introduced.

In both cases, those inefficiencies can be mitigated through register sharing at execution time. In the first case, the destination register can simply be mapped to its source register in the frontend, and the instruction potentially removed from the pipeline depending on the particular micro-architecture [START_REF] Jourdan | A novel renaming scheme to exploit value temporal locality through physical register reuse and unification[END_REF].

Despite constraints due to accesses to partial registers on x86, many instructions can be early executed non-speculatively in the frontend (i.e., in-order) in this fashion. Since Ivy Bridge, Intel processors implement move elimination (ME) [START_REF]Software optimization manual[END_REF].

In the second case, store-load pairs that fit within the processor window can be speculatively identified, and the destination register of the load mapped to the source register of the store [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF][START_REF] Loh | Memory bypassing: Not worth the effort[END_REF]. This is referred to as Speculative Memory Bypassing (SMB). Although the cache will ultimately have to be accessed to validate speculation, this allows dependents on the load to execute at least load-to-use cycles earlier. SMB through the Physical Register File (PRF) has usually been limited to store-load pairs that fit within the instruction window.

Although both optimizations have been extensively covered in previous work [START_REF] Jourdan | A novel renaming scheme to exploit value temporal locality through physical register reuse and unification[END_REF][START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF][START_REF] Tyson | Memory renaming: Fast, early and accurate processing of memory communication[END_REF][START_REF] Moshovos | Streamlining inter-operation memory communication via data dependence prediction[END_REF][START_REF] Moshovos | Read-after-read memory dependence prediction[END_REF][START_REF] Loh | Memory bypassing: Not worth the effort[END_REF], studies that implement sharing through the PRF [START_REF] Jourdan | A novel renaming scheme to exploit value temporal locality through physical register reuse and unification[END_REF][START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF][START_REF] Moshovos | Streamlining inter-operation memory communication via data dependence prediction[END_REF] generally failed to precisely describe how register sharing is actually handled. Most studies consider the adjunction of a reference counter to each physical register. The counter is incremented each time the register is assigned as the destination of an instruction, and decremented when an instruction would usually free the register. Mispredictions are handled by sequentially walking through all squashed instructions and decrementing counters accordingly.

We argue that this particular scheme is impractical since 1) The counter array must provision enough logic to increment up to rename-width and decrement commit-width not necessarily distinct registers on each cycle 2) Recovery latency on a branch misprediction may be increased due to the need to scan squashed instruction and decrement their corresponding counters sequentially. In deeply pipelined architectures, the branch misprediction penalty has been shown to be the largest contributor to performance degradation [START_REF] Sprangle | Increasing processor performance by implementing deeper pipelines[END_REF].

Our main contribution consists in an alternative register reference counting scheme that requires low storage. Contrary to reference counters, our scheme supports checkpointing the tracking structure, allowing for a much faster repair of the tracking state on a pipeline flush.

As they are well-known features, we evaluate this scheme on ME and SMB. In the process, we contribute a new implementation of SMB that benefits from a TAGE-like [START_REF] Seznec | A case for (partially) TAgged GEometric history length branch prediction[END_REF] dependency predictor and other optimizations such as load-load bypassing [START_REF] Moshovos | Read-after-read memory dependence prediction[END_REF]. Using ME and SMB, we find that our sharing framework performs on par with an ideal register tracking scheme.

In the remainder of this paper, we first describe ME and SMB in more details before introducing the Inflight Shared Registers Buffer (ISRB), a small checkpointable structure that enables sharing a subset of the physical register file. We then study how ISRB parameters impact SMB and ME and show that only 480 bits of ISRB storage (plus 96 bits per checkpoint) are sufficient to support both SMB and ME at the same time, on our processor configuration.

MOVE ELIMINATION

One of the most intuitive optimization leveraging register sharing is move elimination (ME). It was first proposed by Jourdan et al. [START_REF] Jourdan | A novel renaming scheme to exploit value temporal locality through physical register reuse and unification[END_REF] to address the large number of register-toregister moves in x86 code, since x86 instructions (including x86_64) overwrite one of their source operands. By mapping the destination of the move to the physical register corresponding to its source architectural register, the move can be executed at Rename without consuming a functional unit or an entry in the scheduler.

Move Elimination for x86_64

Although ME appears as very intuitive, the ability to reference partial registers in x86 renders a practical implementation quite complex. First, moves from 16-and 8-bit registers cannot be eliminated. 2 Similarly, moves with zero extension from an 8-bit register cannot be eliminated if the register is the high part of a 16-bit register (e.g., AH for AX). Those rules as summarized in Intel's Optimization Guide [START_REF]Software optimization manual[END_REF].

As a result, even without the issue of register reference counting, ME is not straightforward for x86_64. Yet, it has been implemented in Intel processors since Ivy Bridge [START_REF]Software optimization manual[END_REF] and AMD processors since Phenom [START_REF]Software optimization guide for amd family 10h and 12h processors[END_REF].

Reference Counting

In [START_REF] Jourdan | A novel renaming scheme to exploit value temporal locality through physical register reuse and unification[END_REF], reference counting is done by associating one counter to each physical register. How counters are rolled back on a pipeline squash is not covered in the paper, hence we assume that instructions on the wrong path are processed sequentially (potentially by chunks) and their associated counter is decremented.

Similarly, Intel does not disclose how reference counting is implemented. However, Intel's documentation [START_REF]Intel 64 and ia-32 architectures software developers manual[END_REF] and a patent [START_REF] Raikin | Tracking mechanism coupled to retirement in reorder buffer for indicating sharing logical registers of physical register in record indexed by logical register[END_REF] hint that not all physical registers are tracked by the reference counting mechanism. Indeed, among the performance events that are available on current generation processors, one relates to unsuccessful move eliminations [START_REF]Intel 64 and ia-32 architectures software developers manual[END_REF]. In particular, it tracks the "Number of integer Move Elimination candidate uops that were not eliminated". A similar event exists for SIMD moves.

To our knowledge, the only reason for which a move would not be eliminated would be if the number of registers shared at any given time were limited. This assumption is backed up by the existence of a patent regarding a possible implementation of ME [START_REF] Raikin | Tracking mechanism coupled to retirement in reorder buffer for indicating sharing logical registers of physical register in record indexed by logical register[END_REF]. It states that when a move elimination 2 Moves from 32-bit registers can be eliminated since x86_64 states that the most significant 32 bits of the larger 64-bit register are set to zero on a 32-bit register-to-register move. This is not the case for 16-and 8-bit moves. takes place, an entry is allocated in a structure, the Multiple Instantiation Table (MIT), which has only a few entries (e.g., 8). We will describe the MIT in more details in Section 4

SPECULATIVE MEMORY BYPASSING

Background.

Another optimization leveraging register sharing can be applied to store-load pairs that fit within the instruction window. Instead of going through the Store Queue (SQ) and copying the data of a store to the destination register of a dependent load, it is much more efficient to rename the destination register of the load to the source register of the store, i.e., perform Speculative memory Bypassing (SMB) directly through the Physical Register File (PRF) [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF]. An alternative is to use a dedicated buffer for SMB [START_REF] Tyson | Memory renaming: Fast, early and accurate processing of memory communication[END_REF], which alleviates the need for register reference counting, but does not leverage the presence of the load data in the PRF. Bypassing can also be applied to load-load pairs [START_REF] Moshovos | Read-after-read memory dependence prediction[END_REF][START_REF] Önder | Load and store reuse using register file contents[END_REF] by renaming the destination register of the second load to the destination register of the first one. This allows a register that was first bypassed through a store to continue feeding redundant loads even though the initial store has left the instruction window.

It has previously been argued that SMB brings marginal speedup if the memory dependency predictor is very accurate [START_REF] Loh | Memory bypassing: Not worth the effort[END_REF]. However, we point out that first, considering load-load pairs increases potential by allowing a single register to propagate for a longer time [START_REF] Moshovos | Read-after-read memory dependence prediction[END_REF].

Second, [START_REF] Loh | Memory bypassing: Not worth the effort[END_REF] assumes the store-to-load forwarding (STLF) latency is a single cycle. In modern processors, the STLF latency is often not disclosed. But it is very unlikely to be a single cycle due to the necessity to 1) CAM the whole SQ 2) Handle specific cases such as operations with different sizes 3) Arbitrate potentially multiple hits using age-based encoding 4) Drive the data out of the SQ. For instance, Agner Fog's well-known optimization guide [START_REF] Fog | The microarchitecture of Intel, AMD and VIA CPUs/An optimization guide for assembly programmers and compiler makers[END_REF] reports at least 3 cycles for AMD Jaguar (8 for Bobcat). Additionally, in the case where the STLF latency is higher than the L1 hit latency (e.g., Bobcat [START_REF] Fog | The microarchitecture of Intel, AMD and VIA CPUs/An optimization guide for assembly programmers and compiler makers[END_REF]), a scheduling mispeculation3 [START_REF] Kim | Understanding scheduling replay schemes[END_REF] will most likely take place every time store data gets forwarded to a load. SMB could prevent this from happening.

Finally, a larger instruction window increases potential by allowing to bypass from older instructions. [START_REF] Loh | Memory bypassing: Not worth the effort[END_REF] considered a much smaller window than windows of current microarchitectures (128-entry vs. 192-entry for Intel Haswell and 224entry for Skylake). As a result, SMB may yet be beneficial to "big cores" that are aiming at sequential performance.

An Improved SMB Implementation.

Ultimately, we choose SMB as a way to evaluate our framework for physical register sharing, because is has been extensively studied in the literature [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF][START_REF] Tyson | Memory renaming: Fast, early and accurate processing of memory communication[END_REF][START_REF] Moshovos | Streamlining inter-operation memory communication via data dependence prediction[END_REF][START_REF] Loh | Memory bypassing: Not worth the effort[END_REF]. Nonetheless, we still consider several improvements over existing SMB mechanisms.

First, we introduce the Instruction Distance predictor, in- This TAGE-like [START_REF] Seznec | A case for (partially) TAgged GEometric history length branch prediction[END_REF] predictor is accessed with the load PC and the global branch history, which are both available in the frontend. It predicts the distance between a load and the instruction producing the data that was read by the corresponding store. With this value, we can produce a ROB index and retrieve the bypass register identifier. We show that this predictor is more efficient at capturing SMB potential than the predictor used in NoSQ [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF]. Second, we generalize SMB to load-load pairs, allowing a single physical register to be shared for a longer duration.

In addition to uncovering more potential performance, this allows to stress the register sharing mechanism even more.

Third, indexing in the ROB allows bypassing from recently committed instructions in addition to inflight ones. As a result, we can study the impact of allowing SMB to span beyond the instruction window.

Instruction Distance Predictor

Computing the Distance.

Figure 1 depicts how the Instruction Distance predictor is able to capture the dependency between a load and an instruction producing the data sourced by the corresponding store. The predictor has two components: the Data Dependency Table (DDT) identifies pairs of instructions after retirement, while the actual predictor provides a distance to each load instruction in the frontend. Only the DDT is shown in the Figure . In the example, two stores to the same virtual address (but through different pointers) are followed by a load from that address. The load is dependent on store 4 and therefore uses the register produced by sub 2 .

The dependency is identified in two steps. First, at Commit, the Commit Sequence Number (CSN) of register-defining instructions (e.g., add 1 ) is written in the Commit Rename Map entry corresponding to the destination architectural register. Second, when a store commits, it reads the Commit Rename Map for the CSN of the instruction that produced the data it stored. The DDT is then accessed using the virtual address the store wrote to and the CSN is written in the DDT entry.

As a result, the DDT will first record the CSN of add 1 (producer of store 3 ), whose value is 0, before recording the CSN of sub 2 (producer of store 4 ) since pointers p and q alias to the same location. At that time, the CSN in the DDT entry is 1.

Then, when load 5 commits, it will read the entry corresponding to pointer p and find the CSN of sub 2 , i.e., 1. Since the CSN is incremented every time an instruction commits, the current CSN for load 5 is 4, and the Instruction Distance can be computed by subtracting the current CSN with the one retrieved from the DDT. Finally, load 5 also puts its CSN in the Commit Rename Map as it produces ar2.

To generalize SMB to load-load pairs, the CSN of load instructions simply has to be put in the DDT after the old CSN has been read from the entry (not shown in Figure 1). Consequently, the Instruction Distance predictor can seamlessly handle load-load pairs.

Predicting the Distance.

The identified dependency is then transferred to the second component of the prediction infrastructure: the actual predictor that will be accessed by subsequent instances of the load in the frontend. We consider two predictors. First, one similar to the one used in NoSQ [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF]. That is, we implement two tables, one is indexed via the load PC only, and the second via a hash of the load-PC, the global branch history and the path history 4 . If both hit, then the path-indexed table provides the prediction. On a misprediction, an entry is allocated in both tables. A confidence counter is associated to each entry, and SMB is only performed if the counter is saturated. The counter is incremented on a correct prediction, and reset to 0 if the distance does not match. Since mispredicting is costly (vs. not predicting at all), counters saturate at 15 (4-bit counters). Note that we only consider a predictor similar to NoSQ's, but not the whole NoSQ infrastructure.

Second, we consider a TAGE-like [START_REF] Seznec | A case for (partially) TAgged GEometric history length branch prediction[END_REF] predictor that features one direct mapped table (the base component) and five partially tagged components that are indexed using the PC, the global branch history, and the path history. We mix respectively 2, 5, 11, 27 and 64 bits of global branch history with 16 bits of path history and the PC to index the different components. The number of entries in each table are respectively 4096 (base table, 5b tag), 512 (10b tag), 512 (10b tag), 256 (11b tag), 128 (11b tag) and 128 (12b tag). Since the distance cannot be greater than the ROB size (plus instructions in flight from Rename to Dispatch, i.e., less than 256 instruc-tions total in our framework), 8-bit distance fields are sufficient, and 4-bit confidence counters are used, as previously. This predictor requires 12.2KB of storage, to be compared to the 17KB we allocate to the predictor of Sha et al. [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF] (4Kentry for each table, 5b tag). We consider asymmetric sizes to illustrate the fact that more refined algorithms are required for SMB to be efficient, as we will show that our TAGE-like scheme outperforms the more conventional predictor in most cases. To that extent, we consider a very large 16K-entry DDT as a first design point.

Nonetheless, we found that using a 8.6KB DDT (1K entries containing the 64-bit virtual address5 a 5b tag) yields an IPC that is within 2.2% (0.7% gmean) of using an unlimited DDT, except in one benchmark out of 36 (hmmer, speedup is 1.03 vs. 1.17). As a result, the overall cost of this embodiment of SMB would be around 21KB.

Since this paper's first goal is to introduce a new register sharing scheme, we did not tune our Instruction Distance Predictor for memory dependency prediction, hence we still use a discrete memory dependency predictor (Store Sets [START_REF] Chrysos | Memory dependence prediction using store sets[END_REF]). As a result, SMB can improve performance because 1) The STLF latency may be hidden 2) False dependencies generated by the Store Sets predictor can be removed by bypassing the register 3) Dependencies missed by the Store Sets predictor can be identified by SMB, reducing the number of memory traps (RAW memory violations).

Nonetheless, it is our intuition that the Instruction Distance Predictor could also act as the memory dependency predictor, although tuning may be required. This would help amortize the cost of the SMB infrastructure and this approach is in fact used in NoSQ [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF], although only store-load SMB is considered in that case. We leave the design of a TAGE-like memory dependency predictor for future work.

Breaking Memory Dependencies Through the Renamer

The distance predictor identifies the instruction producing the result of a load. The Reorder Buffer (ROB) can be used to retrieve the identifier of the physical register produced by this instruction. Once a pair is identified using the Instruction Distance, we simply rename the destination of the load instruction to the destination of the matching instruction.

Figure 2 depicts how this flavour of SMB processes a simple snippet of code. First, sub 1 is allocated an entry in the ROB at Dispatch (1). Then, when load 3 is fetched or decoded, it accesses the Instruction Distance predictor to retrieve how far the instruction producing the data it is expected to load is, if there is one [START_REF]Software optimization manual[END_REF]. If the Instruction Distance falls within the bounds of the ROB, the physical register identifier of the producing instruction is retrieved (3). In particular, the instruction of interest is either: i In flight between Rename and Dispatch. In that case, we consider that the physical register identifier is reachable from a queue of instructions pending allocation in the ROB. ii In the ROB. The ROB entry is accessed and the register identifier retrieved. iii Already out of the ROB as it has committed. No speculation takes place in that case.

Finally, the identifier is used by the Renamer as the new destination register for the load's architectural destination register. This replaces the chain of three dependencies between sub 1 and add 4 by a single register dependency (4).

Validation.

Validation is done by reading the bypassed register when the load issues, and comparing it against the data coming from the memory hierarchy at Writeback. Consequently, it is required that the bypassed register be marked as a source of the load instruction. This may be problematic since the "free" dependency of load instructions is generally used to implement memory dependency predictions. That is, in the scheduler, load instructions may have an extra source operand that corresponds to the store they are predicted to depend on. This is not problematic since loads have one less source operand than stores by construction.

However, since we require loads to depend on yet another instruction, we must make sure that this additional dependency can co-exist with the memory dependency prediction in the scheduler. The most straightforward approach would be to use the Distance predictor as the memory dependency predictor, as in NoSQ [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF]. Yet, because we do not implement the whole NoSQ infrastructure and since we did not tune the Distance predictor to handle memory dependency predictions well, we assume the presence of enough sources in the scheduler, which is optimistic but not unrealistic. For instance, AMD Bulldozer's scheduler supports 4 sources per instruction [START_REF] Golden | 40-entry unified out-of-order scheduler and integer execution unit for the AMD Bulldozer x86_64 core[END_REF], which would be enough for both additional dependencies.

Regardless, this also implies one additional read port on the register file per issued load per cycle. Fortunately, since not all loads are bypassed, and many modern microarchitectures can only issue two loads per cycle at most (e.g., Intel Haswell), the overhead remains limited.

Bypassing from Committed Instructions

In the previous paragraphs, we stated that once the Instruction Distance of a load is predicted, the instruction of interest can be in three distinct states: pending allocation in the ROB, in the ROB, and committed. In the first two cases, SMB can take place, while in the third case, nothing can happen since the instruction has left the ROB.

However, bypassing from recently committed instructions is possible provided that we guarantee that the physical register is still valid. For this purpose, we propose a simple modification of the commit phase in the pipeline. Indeed, a possible implementation of the ROB is to use a circular buffer, with older instructions at the head and younger ones at the tail. Two pointers are responsible for delimiting occupied entries from free entries, that is, when an instruction is added, the tail pointer is incremented, while the head pointer is incremented when an instruction commits. At the same time as an instruction commits, it also releases the previous physical register mapped to its architectural register target. However, data (register numbers, etc.) remain in the ROB entry till the entry is overwritten, i.e., until a new instruction is added to the ROB and the tail pointer has reached this entry.

Therefore, we simply propose to delay the reclaiming of registers after commit as late as possible. A third pointer -release_head -that points to the oldest retired entry containing valid state is used for the register reclaiming process. In this context, the destination register identifier of the instruction contained in the ROB entry is guaranteed not to have been overwritten and can therefore be bypassed.

We reclaim registers lazily, e.g., when the Free List signals that only a few free registers are available or when the ROB is almost full i.e., the tail pointer approaches the release_head pointer. In that event, post-commit hardware scans the ROB starting from the release_head pointer and frees physical registers corresponding to old versions of architectural registers redefined by the committed ROB entries.

Using this mechanism, there is more potential for SMB since registers belonging to committed instructions are still reachable. As the size of the ROB grows, potential should increase even more since more committed state can be kept.

Our proposal should be contrasted with NoSQ [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF]. In that proposal, the Store Register Queue (SRQ) has to remove store source registers as stores are committed, by construction. Indeed, once a store commits, its source register may be reallocated to another instruction in the near future, and it cannot be bypassed safely anymore. Therefore, using the ROB for SMB can uncover more potential.

REGISTER REFERENCE COUNTING

Both ME and SMB through the register file require register reference counting to avoid reclaiming a live register. In general, per-register counters are considered, yet we argued in Section 1 that they might not be practical enough, in particular during pipeline flushes. In this Section, we first describe how the Renamer state can be rolled back on a pipeline flush. Then, we review three previously proposed register sharing schemes and illustrate their shortcomings. Finally, we propose a new scheme that can track enough registers to not hold back ME and SMB while requiring limited storage and being checkpointable.

Recovery in a Regular Register Renamer

A commonly depicted renamer consists of three structures: 1) The Rename Map (RM), that maps architectural registers to physical registers 2) The Free List (FL), a circular buffer that contains free physical registers and 3) The Commit Re-name Map (CRM), that contains non-speculative mappings. When an instruction is renamed, it first looks for the physical register corresponding to its source architectural registers in the RM. Then, it takes a free register at the head of the FL and places it in the RM entry corresponding to its architectural destination register.

Assuming a checkpointing architecture where the RM and FL pointer are checkpointed (e.g., at every low confidence branches [START_REF] Akkary | Checkpoint processing and recovery: towards scalable large instruction window processors[END_REF]), recovering from a pipeline flush implies copying the checkpointed RM to the processor's RM and restoring the FL pointer. For pipeline squashes taking place at Commit (e.g., value mispredictions [START_REF] Perais | Practical data value speculation for future high-end processors[END_REF]), copying the CRM in the RM and restoring the Committed FL pointer are sufficient (i.e., no checkpointing is necessary).

As a result, recovering the renamer state on a branch misprediction is fairly simple and can be done in a single cycle if a checkpointing architecture is implemented [START_REF] Leibholz | The Alpha 21264: a 500 MHz out-of-order execution microprocessor[END_REF][START_REF] Yeager | The MIPS R10000 superscalar microprocessor[END_REF]. Unfortunately, allowing registers to be shared complicates this process. For instance, per-register counters cannot be checkpointed, by construction. This is problematic since the branch misprediction recovery latency has been shown to strongly contribute to deeply pipelined processors performance [START_REF] Sprangle | Increasing processor performance by implementing deeper pipelines[END_REF]. As a result, there is a call for a sharing scheme that would allow such a simple recovery process for the renamer state.

Previous Proposals for Reference Counting

2D Matrices.

Roth [START_REF] Roth | Physical register reference counting[END_REF] describes two ways to count register references. First, through a 2D matrix whose columns correspond with physical registers and rows correspond with ROB entries. A set bit means that the ROB entry corresponding to the row references the physical register corresponding to the column. As a result, a register is free if the OR of all rows returns 0. However, this design appears impractical for a modern processor such as Intel Haswell (192-entry ROB, 168 INT regs, 168 FP/SIMD regs). The matrix would require a 2 × 192 × 168 bits, amounting to around 7.8KB of storage (not even counting the columns dedicated to the Commit Rename Map). As a comparison, the matrix of a baseline matrix scheduler the size of Haswell's would require 0.44KB only. One could argue that 7.8KB is not so high a cost to pay for reference counting. This may be true now, but due to its matrix nature, we would argue that it is intrinsically not scalable anyway.

Battle et al. improve on this scheme by diminishing the matrix requirements [START_REF] Battle | Flexible register management using reference counting[END_REF].The matrix only requires #preg × max_sharers_per_register bits, but is entirely checkpointed in a processor using checkpoints, i.e., checkpoint storage is still significant.

Reference Counters.

Second, references can be counted through implementing one counter per physical register and incrementing it on allocation or re-reference 6 while decrementing it on regular deallocation and de-reference. The value of the counter gives the state of the register: if the counter is 0, the register is free, otherwise, it is not. Counters appear as the most intuitive way to count references. However, a problem arises for squashes.

In a checkpointing architecture that allows register sharing, reference counters need to be rolled back in addition to the RM and the FL pointer. This is problematic because their value cannot simply be checkpointed and restored. The reason is that a counter can have been decremented when an instruction older than the checkpoint committed. Restoring the checkpointed value would consider that the older instruction has not committed, and the pointed physical register would therefore never be freed.

As a result, squashing implies walking the squashed instructions and decrementing reference counters. That is, the pipeline cannot restart immediately because the ROB has to be walked sequentially (potentially by chunks). While this might have little to moderate impact on performance [START_REF] Akkary | Checkpoint processing and recovery: towards scalable large instruction window processors[END_REF], it complicates the recovery process and should be avoided for deeply pipelined processors [START_REF] Sprangle | Increasing processor performance by implementing deeper pipelines[END_REF].

Enabling fast recovery for reference counters would imply 1) Updating the most recent checkpoint each time an instruction references a register and all checkpoints each time an older instruction commits 2) Having enough storage in each checkpoint for every register of the processor (i.e., at least a few bits for each of the 336 registers of Haswell). While updating checkpoints on the fly may be doable, increasing the size of each checkpoint by 600+ bits may not be desirable.

Multiple Instance Table (MIT).

The MIT, introduced in an Intel patent of Raikin et al. [START_REF] Raikin | Tracking mechanism coupled to retirement in reorder buffer for indicating sharing logical registers of physical register in record indexed by logical register[END_REF], allows potentially limited register sharing capacity. It appears as small fully-associative structure of which an entry is allocated when a move elimination candidate is encountered. Each entry contains a bit-vector corresponding to architectural registers, e.g., if bits 0 and 1 are set, then both rax and rbx map to the physical register. A bit is reset when the corresponding architectural register is redefined, and if the whole vector is zero, then the physical register is freed.

However, the MIT leverages the property of move elimination that both architectural registers pointing to the physical register are known since they are visible in the move instruction. This is not the case for SMB as the source architectural register of the store has potentially already been re-renamed when the matching load is renamed (store-load case). In other words, the MIT cannot track sharing in SMB, because the algorithm is based on architectural names. Moreover, it requires more checkpoint storage per entry than the scheme we propose (#arch_reg bits per entry).

Register Duplicate Array (RDA).

Lastly, the RDA is described in an Apple patent of Sundar et al. [START_REF] Sundar | RDA checkpoint optimization[END_REF]. Similarly to the MIT, it is a small fully associative structures where entries are allocated and de-allocated on-demand. Each entry contains a reference counter which tracks the number of sharers. As a result, contrary to the MIT, it is not limited to move elimination. However, to make the structure checkpointable, all counters (in the RDA and checkpointed) relating to the physical register of interest must be updated when an instruction retires. In other words, committing a mapping relating to a tracked physical register requires decrementing up to n counters, with n the number of checkpoints.

Limited Reference Counting

A Single Counter Isn't Enough

We previously stated that the value of a reference counter cannot be checkpointed since the number of sharers is modified by the Commit stage. However, we observe that by using two counters per register instead of one, checkpoints can be used. A first counter, referenced is incremented when a register is bypassed (i.e., not allocated from the Free List). For instance, in the case of SMB, an instruction feeding a store will be allocated a register, but the bypassed counter will not be touched. It is only when the bypassing load enters Rename that it will be incremented, since there is one more bypassing instruction referencing this register.

A second counter, committed, is increased when an instruction that overwrites one of the architectural register referenced by the physical register commits. Given the previous example, the committed field will be incremented when an instruction that writes the same architectural register as either the bypassing load or the instruction feeding the associated store is committed.

It follows that if referenced is equal to committed, then the register can be freed by the next committing instruction that overwrites the mapping containing the physical register. At that time, both counters will be reset. In the remainder of the paper, we refer to committed and referenced as counters, but it should be noted that those structures are really up-counters that can be reset, i.e., they are never decremented.

Checkpointing.

This dual-counter scheme lends itself to checkpointing because it differentiates between the number of committed references and the total number of references (which includes committed references). Indeed, the number of committed references is architectural, therefore, it is always correct. Only the total number of references may be stale after a pipeline flush, if squashed instructions did reference the register on the wrong path.

As a result, checkpointing the referenced field only allows to restore the reference counting mechanism to a correct state straightforwardly on a pipeline flush: Checkpointed values simply have to be restored. There is however a specific case where additional steps must be taken to ensure proper recovery, but this does not increase recovery latency, as we illustrate in the following example.

Working Example.

Figure 3 provides an example of how this dual-counter scheme is able to track how many times a register is bypassed in the presence of a branch misprediction. While it can handle both SMB and ME, we focus on SMB to give a non-trivial example. In the Figure, the referenced counter of register p1 is incremented to 1 when load 4 hits p1 in the ROB. Subsequently, a branch, jmp 8 , is encountered and referenced is checkpointed. Past the predicted non-taken branch, load 10 also hits p1 in the ROB and referenced is incremented to 2.

At some point, shl 3 and sub 7 are committed. Since both overwrite mappings containing p1 (respectively rax => p1 of sub 1 and rbx => p1 of load 4 ), the committed counter of p1 is incremented two times and reaches 2, the same value as referenced. This means that when the instruction that overwrites the mapping of load 10 (rdx => p1) commits, it will free p1 and reset both counters.

Unfortunately, jmp 8 was mispredicted. To recover, the state contained in the checkpoint for p1 is copied to the referenced field, correctly reflecting the fact that there is only one instruction using p1 through SMB (load 4 ). However, since committed is 2 (i.e., greater than referenced), this means that the last instruction that overwrote a mapping containing p1 (i.e., sub 7 ) should have freed p1 and reset both fields.

Consequently, an additional step is required to compare the current committed value to the referenced value of the checkpoint. If committed is strictly greater, the register is freed and both counters are reset. Otherwise, one or more subsequent instructions have a reference to an old mapping containing the register, which will therefore be freed later.

In any case, these operations are quite simple and process narrow values. Therefore, we expect recovery to take a few cycles at most and to be doable in a single cycle. In other words, restoring a correct state can be done in a single cycle. Pushing the registers freed during recovery to the Free List may be done in subsequent cycles, but the processor need not wait for this before restarting Fetch.

Not All Registers Are Shared

We base our final reference counting scheme on the intuition that if a snapshot of the register file had to be taken, most would either be referenced one time only or be free, and a few would be referenced more than one time. Ultimately, the additional state that needs to be checkpointed corresponds to the latter ones, since restoring the Free List pointer covers the ones that are referenced only once.

As a result, we introduce the Inflight Shared Register Buffer (ISRB). Much like the MIT [START_REF] Raikin | Tracking mechanism coupled to retirement in reorder buffer for indicating sharing logical registers of physical register in record indexed by logical register[END_REF] and RDA [START_REF] Sundar | RDA checkpoint optimization[END_REF], the ISRB is a small fully-associative buffer that tracks registers that have currently more than one sharer. Each entry of the ISRB comprises the physical register identifier, that acts as the tag, and the two counters, referenced and committed.

Bypass Potential.

Being able to track a small number of registers has implications on how bypassed registers are processed. First, when a bypassing event is detected (e.g., move elimination or SMB), an ISRB entry is allocated for the physical register. If the ISRB is full, bypassing does not take place. Fortunately, we will show that only 16 to 32 entries are sufficient to capture most of the potential of both ME and SMB.

Register Reclaiming.

The register reclaiming hardware has to CAM the ISRB when it attempts to free every register. On a CAM match, if both counters are equal 7 , then the register and the ISRB entry are freed. In that event, all checkpointed referenced counters Front End L1I 8-way 32KB, 1 cycle, Perfect TLB; 32B fetch buffer (two 16-byte blocks each cycle, potentially over one taken branch) w/ 8-wide fetch, 8-wide decode, 8-wide rename TAGE 1+12 components [START_REF] Seznec | A case for (partially) TAgged GEometric history length branch prediction[END_REF]

Instruction Distance Predictor

NoSQ: 4K(d. map) + 4K(hash) [START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF], 5b tag, 4b conf., 17KB TAGE-like: 1 + 5-comp. [START_REF] Seznec | A case for (partially) TAgged GEometric history length branch prediction[END_REF] (5.25K entry total), 12.2KB DDT Base: 16K-entry DDT (14b tag),156KB; DDT Opt. 1Kentry DDT (5b tag), 8.6KB corresponding to this entry are also gang-reset. Otherwise, the committed counter is incremented. On a mismatch, the register is freed.

Checkpoint Recovery.

Checkpoint recovery simply requires the referenced field of the checkpoint to be copied to the corresponding ISRB entry. In parallel, the committed field is pulled from the ISRB and checked against the checkpointed referenced field. If committed is greater than referenced, the physical register and the ISRB entry are freed, as previously. In addition, if both counters are zero, the ISRB entry is freed, as the physical register has either been freed by restoring the Free List pointer (re-allocation and reuse are younger than the checkpoint) or will be freed when committing an instruction older than the checkpoint (re-allocation is older than the checkpoint, but reuse is younger). If the ISRB entry is already free, nothing happens.

The only requirement for this scheme to ensure correctness is that when an ISRB entry is freed, all corresponding entries in the checkpoints be marked as invalid (i.e., have their referenced counter reset). This takes care of the particular case where an ISRB entry that was freed on the correct path is still tracked in a younger checkpoint. If said checkpoint is not invalidated when the ISRB entry is freed, a wrong referenced value may be restored if the entry has been re-allocated on the wrong path, allowing physical registers to "leak". By resetting checkpoint entries, a value of 0 will be restored for referenced.

Checkpointing Storage Overhead

We previously mentioned that each checkpoint should contain a very limited subset of the ISRB state: the referenced field. This amounts to n-bit counters times the number of ISRB entries. For an 8-entry ISRB and 3-bit counters, this amounts to 24 bits of storage, while a 16-entry ISRB requires 48 bits and a 32-entry ISRB requires 96 bits only. In comparison, saving the x86_64 Rename Map requires at least 256 bits ((16 GPRs + 16 SIMD registers) × 8-bit identifiers).

Complexity of the ISRB

Although it features a small number of entries, the ISRB is a heavily contended structure. Each cycle, it must be associatively searched by the renamer for each register that is a candidate for bypassing. In the meantime, the register reclaiming mechanism must also associatively search the ISRB for every register it attempts to free. This amounts to rename_width + reclaim_width CAM ports in the worst case. Fortunately, the number of ports needed by the renamer can be reduced since only bypassing candidates require a port at rename time.

One could also reduce the number of ports dedicated to register reclaiming through leveraging the fact that not every register is a likely candidate for sharing. That is, only specific instructions need to check the ISRB when they are processed by the register reclaiming mechanism.

By writing a flag in the Rename Map at Rename, and propagating this flag to the instruction that redefines the register, we can avoid many ISRB accesses at reclaiming time. For instance, for ME, the bit is set for both the architectural source and destination registers when the move is eliminated. For SMB, all loads set the bit for their architectural destination register, while all stores set the bit for the architectural register that contains store data. Any other instruction resets the flag of their destination register at Rename.

Then, if an instruction redefines a register whose flag is set, it will check the ISRB for the physical register previously mapped to the architectural register at reclaiming time. Otherwise, the old physical register can be freed without accessing the ISRB.

EVALUATION METHODOLOGY

Simulation Infrastructure

We use the gem5 cycle-level simulator [START_REF] Binkert | The gem5 simulator[END_REF] implementing the x86_64 ISA. We consider a relatively aggressive 4GHz, 6-wide issue pipeline. The fetch-to-commit latency is 19 cycles. The in-order front-end and in-order back-end are overdimensioned to treat up to 8 µ-ops per cycle. We model a deep front-end (15 cycles) coupled to a shallow back-end (4 cycles) to obtain a realistic branch misprediction penalty (20 cycles minimum). We allow two 16-byte blocks of instructions to be fetched each cycle, potentially over a single taken branch. Table 1 describes the characteristics of the baseline pipeline we use in more details.

In our experiments, the store-to-load forwarding latency is equal to the L1 latency (4 cycles), and only loads that are fully or partially contained in inflight stores (e.g., load 32 bits from a 64-bit store) can read data from the Store Queue. Overlapping loads wait for the stores they overlap with to write back.

Lastly, in the version of gem5-x86 we use, all register-toregister moves are merge µ-ops, meaning that a 64-bit move depends on both its source operand and its destination operand [START_REF] Nowatzki | Architectural simulators considered harmful[END_REF]. The latter dependency is not required because the whole destination is overwritten (also the case for 32-bit move). However, if it is not removed, the gains of ME will be overestimated. Consequently, we reimplemented 64 and 32-bit registerto-register moves as true moves while 8-and 16-bit moves remain merge µ-ops. We use a subset of the SPECCPU 2000 [START_REF]CPU2000[END_REF] and SPEC-CPU 2006 [START_REF]CPU2006[END_REF] suites to evaluate our contributions. Specifically, we use 18 integer benchmarks and 18 floating-point programs 8 . We use the reference inputs provided in the SPEC software packages. To get relevant numbers, we identify a region of interest in the benchmark using Simpoint 3.2 [START_REF] Perelman | Picking statistically valid and early simulation points[END_REF]. We simulate the resulting slice of 150M instructions by warming up the caches and branch predictor for 50M instructions then collecting statistics for 100M instructions.

Benchmarks

Figure 4 reports the IPC of each benchmark on the baseline pipeline configuration, as well as the number of memory order violations (traps that result in a pipeline flush in gem5) and the number of false dependencies introduced by the Store Sets predictor. The two latter are reported on a log scale.

EXPERIMENTAL RESULTS

Impact of ISRB Parameters on ME

Impact of the Number of Entries.

Figure 5 (a) illustrates the fact that only a few entries are sufficient to benefit from the speedup brought by move elimination. In this case, we only implement ME for 64-and 32bit integer register to integer register moves. 9 Nonetheless, even limited to integer registers, ME is able to increase performance significantly, up to 5.2% in crafty. As expected, the gain is generally lower for FP benchmarks.

Moreover, we observe that a if 32-entry ISRB is enough to benefit from almost the whole potential of ME, 16 entries are generally sufficient, and 8 entries perform reasonably well. In any case, speedups are generally limited (1% geometric mean), which is in accordance with what Jourdan et al. observed [START_REF] Jourdan | A novel renaming scheme to exploit value temporal locality through physical register reuse and unification[END_REF].

Figure 5 (b) illustrates the percentage of renamed instructions that were eliminated thanks to move elimination (assuming an unlimited ISRB). These instructions are put in the ROB and renamed, but they do not occupy an entry in the outof-order scheduler or an ALU since they are never issued. We note that this proportion does not correlate strongly with the performance gain. For instance, in vortex, almost 10% of the renamed instructions are eliminated, but the gain is less than 3%. Conversely, in namd, only 5% of the renamed instruc- 8 We do not use the whole suites due to some currently missing system calls/x87 instructions in our version of gem5-x86. 9 Recent Intel microarchitectures also implement it for floating point moves and moves with zero extend [START_REF]Software optimization manual[END_REF]. tions are eliminated, but this allows to increase performance by around 4.5%.

Impact of ISRB Parameters on SMB

Number of Entries.

Figure 6 (a) considers the performance gain brought by SMB for both store-load and load-load pairs (bypassing from non-committed instructions only) depending on the number of ISRB entries. Contrary to move elimination, SMB puts more pressure on the ISRB, hence 24 entries are required to achieve almost the full potential of SMB. By lack of space, we do not report numbers for a limited-size DDT, but we found IPC to be within 3% of using an unlimited DDT, except in hammer where speedup would be 3% instead of 17%. However, the use of an associative/skewed table is possible to address this drop. We also note that using a 2-table predictor like NoSQ's does not improve performance much, contrarily to our TAGE-like predictor.

In addition, Figure 6 (b) reports the reduction in number of memory order violations and false memory dependencies when using an unlimited ISRB and our TAGE-like predictor. Those are reported only for benchmarks where those events occur reasonably often in the baseline depicted in Figure 4 (i.e., at least 1K memory traps, and at least 10K false dependencies). We can observe a correlation between the speedup and the reduction of at least one type of event (e.g., wupwise, applu, bzip, gamess, gromacs and hmmer), hinting that SMB itself may not improve performance, but rather, the TAGElike Distance Predictor is able to capture dependencies that Store Sets cannot. Yet, in astar, performance increases but few memory traps and false dependencies take place. In this case, performance increases because the STLF latency is hidden by SMB (i.e., bypassed loads have a latency of 0 instead of 4 cycles). This is not incompatible with [START_REF] Loh | Memory bypassing: Not worth the effort[END_REF], as if we had a perfect memory dependency predictor, then the only source of speedup would be hiding the STLF latency, and speedups would be lower. Yet, since Store Sets is not a perfect predictor, we obtain good speedups in several benchmarks. As a result, those numbers can be seen as a hint that TAGE-like memory dependency prediction may be worthwhile rather than a case for SMB itself.

Lastly, we also considered bypassing only from stores, and found that in a few cases, this was particularly detrimental. By lack of space, we do not report all bars, but specifically, notable decreases include astar (2.8% vs. 16.6%), wupwise (18.7% vs. 21.9%), applu (29.6% vs. 35.3%), bzip (2.0% vs. 9.8%) and hmmer (7.5% vs. 16.9%). The distance predictor accuracy is similar in both cases. This suggests that in those benchmarks, a fair amount of the speedup actually comes from hiding the latency of loads, which can be done more often if load-load bypassing is allowed.

Bypassing from Committed Instructions.

Figure 6 (c) extends SMB to committed instructions that still occupy an entry in the ROB. Register reclaiming is triggered when the Free List signals that only rename_width × 2 free registers are left or when head reaches release_head. We consider an unlimited ISRB and a 24-entry ISRB. The Figure shows that allowing to bypass from recently committed instructions generally has a marginal impact, even though the average percentage of retired loads that were bypassed increases from 32.3% to 35.7% (Unlimited ISRB). This is not unexpected. Indeed, when bypassing from committed instructions, only the L1 latency can be hidden because the Store Sets predictor cannot make a load falsely depend (or miss a dependency) on a committed store (strictly speaking, it can, but this has no performance impact). As a result, improvements are modest. We found this to be true even when the size of the ROB is increased to 512 and the ISRB size is kept unlimited.

Performance decreases significantly in some cases (e.g., wupwise, applu, gamess and gromacs) when the ISRB is of limited size. In that case, less bypassing takes place within the window because some ISRB entries are taken up for bypassing from committed instructions, reducing the amount of ISRB entries used to remove memory traps/false dependencies.

The only exception to this trend is astar. In this benchmark, Store Sets perform quite well (366 memory traps and no false dependencies reported for 100M instructions), yet, regular SMB provided 16.5% speedup, simply by reducing the latency of many loads (53.9% of the committed loads). As a result, it is not surprising that when the STLF latency can be hidden for more loads (59.5% of the committed loads), speedup increases to 20.8%. However, this behavior appears to be the exception, which is in accordance with [START_REF] Loh | Memory bypassing: Not worth the effort[END_REF].

Consequently, if this optimization allows to seamlessly bypass from committed instructions, it does not appear useful in the context of SMB, and we therefore focus on instructions that fit in the window in the remainder of this paper. Lazy reclaim might be considered worthwhile in the context of Register Integration [START_REF] Petric | Three extensions to register integration[END_REF], however.

Combined

Impact of the ISRB Size.

Figure 7 shows speedup over baseline when both SMB and ME are used. If we consider a 32-entry ISRB, performance is often higher than ME or SMB alone (using an unlimited ISRB). 24 entries only also appears as a good tradeoff overall since performance is close to the 32-entry version.

However, using only 16 entries often results in performance being worse than the best of either ME or SMB using an unlimited ISRB. The reason is that both ME and SMB share the ISRB, hence performance decreases in benchmarks that benefit from a single mechanism. An exception is mgrid, where less bypass mispredictions take place because of the limited ISRB, yet enough bypassing still takes place to improve performance slightly.

As a result, for smaller ISRB sizes, it might prove efficient to forbid a single mechanism from using the whole ISRB, e.g., by forbidding ME to be performed if less than n entries are available in the ISRB. We leave the exploration of such mechanism for future work as it depends on which particular combinations of optimizations are implemented.

Counter Width.

We found that using 3-bit counters is sufficient to get within 1.3% (worst case, gmean is 0.1%) of the ideal IPC using both SMB and ME. 10 Using a 32-entry ISRB with 3-bit counters yields an average speedup of 5.5% (geomean), while requiring 480 bits of CPU storage, and 96 bits per additional checkpoint. An unlimited ISRB with 32-bit fields yields an average speedup of 5.6%.

ISRB Accesses.

On our benchmark suite, considering both SMB and ME and a 32-entry ISRB, the average distance (in instructions) between two instructions that attempt to allocate an entry in the ISRB is 19.7 (min. is 3.8). As a result, provisioning less ports than the rename width should not be problematic, especially since SMB or ME can be aborted if not enough ports are available (stalling is not necessary).

Similarly, on our benchmark suite, the average between committing instructions that check the ISRB is 3.4 (min. 2.3). As a result, more ports are for reclaiming, especially since those accesses must be made to enforce correctness. Since up to 53% (32% average) of the instructions needing access to the ISRB at reclaiming are im-mediately followed by an instruction that also needs access to the ISRB, provisioning 6 ports for a commit-width of 8 should prevent Commit from stalling in the general case.

OTHER RELATED WORKS

Non Sharing-based Schemes

Tyson et al. [START_REF] Tyson | Memory renaming: Fast, early and accurate processing of memory communication[END_REF] implement speculative memory bypassing for store-load pairs through a dedicated buffer, alleviating the need for register sharing, but not taking advantage of the fact that values are already in the PRF.

Önder and Gupta propose to associate a memory address to each physical register [START_REF] Önder | Load and store reuse using register file contents[END_REF]. An issuing load can then check if a register already contains the value located at the address it is accessing before accessing the L1 Cache. Silent stores can also be eliminated through this technique. Unfortunately, this technique would be very expensive to implement in a modern superscalar processor, as each issued memory instruction must associatively access #phys_reg virtual addresses. For instance, on Haswell, the PRF has 168 INT and 168 FP/SIMD registers and three addresses can be generated each cycle.

Similarly, Yang and Gupta [START_REF] Yang | Energy-efficient load and store reuse[END_REF] describe a mechanism where load and store reuse is attempted before sending memory instructions to the cache. The main difference with Onder and Gupta [START_REF] Önder | Load and store reuse using register file contents[END_REF] is that bypassing is done through a PC-based directmapped table rather than by associatively searching the whole register file on every access. To predict, the load PC is used to index the Load Table (LT) before the cache access. The LT entry contains an address, and on a match, the value in the entry can be reused (same-load reuse). Otherwise, another table is accessed to try different-load reuse. This table contains a pointer to another entry of the LT. If this fails, the same process is attempted by accessing another table containing pointers to the Store Table (store-load reuse). The cache is accessed if none of the three reuse types can take place. Note that to identify different load reuse and store-to-load reuse (i.e., train the tables containing the pointers to the LT and ST), associatively searching the LT and ST on the address field is still required.

Sodani and Sohi propose instruction reuse in which instructions (including loads) can produce their result faster by checking in the Reuse Buffer (RB) if its operands correspond to past operands [START_REF] Sodani | Dynamic instruction reuse[END_REF]. If it is the case, the result is directly available from the RB. As in the two previous schemes [START_REF] Önder | Load and store reuse using register file contents[END_REF][START_REF] Yang | Energy-efficient load and store reuse[END_REF], the RB must be kept coherent with memory.

Sharing-based Schemes

Jourdan et al. [START_REF] Jourdan | A novel renaming scheme to exploit value temporal locality through physical register reuse and unification[END_REF] generalize register sharing by comparing the result of an instruction to recently produced results contained in a buffer. On a match, the new instruction can be renamed to the register containing the recently produced value. However, since this comparison must be done before renaming takes place, it requires that the younger instruction be value predicted, a load immediate, or that sharing be added on top of instruction reuse [START_REF] Sodani | Dynamic instruction reuse[END_REF] or Virtual Registers [START_REF] Gonzalez | Virtual-physical registers[END_REF]. Register sharing is achieved through counters.

Petric et al. propose RENO, a rename-time hardware optimizer [START_REF] Petric | Reno: a rename-based instruction optimizer[END_REF]. RENO is able to perform move elimination and non-speculative memory bypassing, amongst others. Yet, it relies on per-register counter for register sharing. Fortunately, since RENO is able to dynamically eliminate up to 22% of the dynamic instructions of SPECint2000 (i.e., not all registers are shared), we believe that using the ISRB would not hinder its performance.

Fahs et al. propose Continuous Optimization (CO) [START_REF] Fahs | Continuous optimization[END_REF]. CO is similar to RENO in the optimizations that it can perform dynamically, and also uses per-register counters to implement register sharing. As for RENO, using a limited counting scheme such as the ISRB should be straightforward.

Finally, Petric et al. [START_REF] Petric | Three extensions to register integration[END_REF] propose an optimized implementation of register integration that addresses the same inefficiencies as instruction reuse [START_REF] Sodani | Dynamic instruction reuse[END_REF] and the generalized register sharing scheme of Jourdan et al. [START_REF] Jourdan | A novel renaming scheme to exploit value temporal locality through physical register reuse and unification[END_REF]. Integration (reuse) opportunities are identified using register names only, contrary to [START_REF] Jourdan | A novel renaming scheme to exploit value temporal locality through physical register reuse and unification[END_REF][START_REF] Sodani | Dynamic instruction reuse[END_REF], therefore reuse is identified in the frontend. Yet, register sharing is once again achieved through per-register counters.

CONCLUSION

Move elimination (ME) is a currently implemented optimization that mitigates the high number of register-to-register moves in x86. Speculative Memory Bypassing (SMB), while not implemented to our knowledge, is an attractive solution to mitigate the cost of communicating results through the memory hierarchy rather than registers, although it has been shown to be of limited interest in the presence of a good memory dependency predictor [START_REF] Loh | Memory bypassing: Not worth the effort[END_REF].

Both optimizations require the ability for physical registers to be shared by several instructions, yet previously proposed mechanisms were either too limited (e.g., MIT [START_REF] Raikin | Tracking mechanism coupled to retirement in reorder buffer for indicating sharing logical registers of physical register in record indexed by logical register[END_REF]), or too costly/unadapted in case of pipeline flushes [START_REF] Roth | Physical register reference counting[END_REF].

In this work, we first proposed an implementation of SMB that identifies both load-load and store-load pairs through a TAGE-like Instruction Distance Predictor. Using this distance, a ROB index is generated and the physical register identifier to be used by the bypassing instruction is retrieved. We also pointed out that since the ROB is used to bypass, recently committed instructions are still reachable for SMB. However, on our benchmark set, bypassing from recently committed instructions did not improve performance noticeably and was in fact often detrimental.

Second, and more importantly, we proposed a register sharing mechanism that can be adapted to any optimization requiring sharing, and that lends itself to checkpointing. That is, correct state can be recovered on a pipeline flush by restoring checkpointed state and simple comparisons on narrow values. Hence, recovery can be done in a single cycle.

Finally, we considered using a small fully-associative buffer, the ISRB, implementing our tracking mechanism for a subset of the physical registers. We showed that only 32 entries of two 3-bit fields are required to obtain most of the potential of both ME and SMB. In particular, average speedup is 5.5% and up to 39.6%. We point out that considering only one of both mechanisms puts less pressure on the ISRB, hence less entries need to be implemented (respectively 16/8 for ME and 24/16 for SMB).

Figure 1 :

 1 Figure 1: Computing the Instruction Distance of load 5 at Commit.spired from the Store Distance predictor of Sha et al.[START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF]. This TAGE-like[START_REF] Seznec | A case for (partially) TAgged GEometric history length branch prediction[END_REF] predictor is accessed with the load PC and the global branch history, which are both available in the frontend. It predicts the distance between a load and the instruction producing the data that was read by the corresponding store. With this value, we can produce a ROB index and retrieve the bypass register identifier. We show that this predictor is more efficient at capturing SMB potential than the predictor used in NoSQ[START_REF] Sha | NoSQ: Store-load communication without a store queue[END_REF].Second, we generalize SMB to load-load pairs, allowing a single physical register to be shared for a longer duration.In addition to uncovering more potential performance, this allows to stress the register sharing mechanism even more.Third, indexing in the ROB allows bypassing from recently committed instructions in addition to inflight ones. As a result, we can study the impact of allowing SMB to span beyond the instruction window.

Figure 2 :

 2 Figure 2: Memory dependency collapsing through renaming.

Figure 3 :

 3 Figure 3: Register Counting using the Inflight Shared Registers Buffer.

Figure 4 :

 4 Figure 4: IPC, memory traps (logscale) and false memory dependencies (logscale) on the baseline architecture.

  (a) Varying the number of entries. (b) Percentage of renamed instructions that were eliminated (Unlimited ISRB).

Figure 5 :

 5 Figure 5: Impact of ISRB parameters on the performance gain (speedup over baseline) brought by move elimination.

Figure 6 :

 6 Figure 6: Impact of ISRB parameters on the performance gain (speedup over baseline) brought by SMB.

Figure 7 :

 7 Figure 7: Speedup brought by the combination of ME and SMB, depending on the ISRB size.

  15K entry total, 20 cycles min. mis. penalty; 2-way 4K-entry BTB, 32-entry RAS;

		192-entry ROB, 60-entry IQ unified, 72/48-entry LQ/SQ (STLF
		lat. 4 cycles), 256/256 INT/FP; 4K-SSID/LFST Store Sets,
	Execution	not rolled-back on squash[16]; 6-issue, 4ALU(1c), 1Mul-
		Div(3c/25c*), 2FP(3c), 2FPMulDiv(5c/10c*), 2Ld/Str, 1Str;
		Full bypass; 8-wide retire
		L1D 8-way 32KB, 4 cycles, 64 MSHRs, 2 load ports; Unified
	Caches	L2 16-way 1MB, 12 cycles, 64 MSHRs, no port constraints, Stride prefetcher, degree 8, distance 1; All caches have 64B
		lines and LRU replacement;
		Single channel DDR3-1600 (11-11-11), 2 ranks, 8 banks/rank,
	Memory	8K row-buffer, tREFI 7.8us; Across a 64B bus; Min. Read Lat.:
		75 cycles, Max. 185 cycles.

Table 1 :

 1 Simulator configuration overview. *not pipelined.

Load dependents were speculatively scheduled assuming that the load was going to hit in the L1, but they will not find their inputs on the bypass network because the load has been delayed by STLF.

Since we use large tables for this predictor, we XOR 8 bits of the global branch history with 8 bits of the path history, and XOR them with the load's address left-shifted by 4 bits.

Caching the -usually smaller -physical address is possible and preferable if SMT is implemented, but this requires one or more TLB ports to update the DDT, or caching translations in the LQ/SQ until instructions update the DDT.

For instance, a load that uses its producer store's source register as its destination register re-references the register.

This can be checked easily by computing NOR bitwise (referenced XOR bitwise committed). Since the fields are small (we found 3 bits to be sufficient), this should be fast and quite cheap.

ME actually performs well on all benchmarks but one when singlebit counters are used. This would facilitate recovery by removing the need to compare fields, and is therefore a valid design point if only ME is considered.

Acknowledgments

This work was partially supported by the European Research Council Advanced Grant DAL No. 267175


Jean-Philippe Lambert
email: lambert@ircam.fr

Sébastien Robaszkiewicz
email: robaszkiewicz@ircam.fr

Norbert Schnell
email: schnell@ircam.fr

Synchronisation for Distributed Audio Rendering over Heterogeneous Devices, in HTML5

Keywords: CCS Concepts, Applied computing → Sound and music computing, •Networks → Time synchronization protocols, •Computer systems organization → Distributed architectures, Realtime systems, Synchronisation, HTML5, Web Audio API, Audio, Distributed

The HTML5 standard is wide-spread on mobile devices. In combination with the Web Audio API, it allows for massively distributed real-time audio rendering. But timing issues exist, mainly because of the lack of standard inter-device synchronisation. This paper proposes a synchronisation solution based on HTML5. Using a shared reference time, we achieved the distributed rendering of audio events with an individual accuracy of 1 to 10 ms, 5 ms in standard deviation, which is more accurate than the audio block duration, for any device that we measured.

INTRODUCTION

The generalisation of mobile devices that embed facilities for real-time audio, processing, motion sensors, and networking, has made it easy to use them for a wide range of applications. The fifth major revision of the Hypertext Markup Language (HTML5) [START_REF]W3C[END_REF] grants access to these features in a Web page from a standard Web browser, instead of developing native applications. Massively distributed applications are now within the reach of anyone, and this is of particular interest for audio applications, as one can distribute a complete audio process to a mobile device, up to an integrated speaker.

However, various platforms exhibit various behaviours. First, the devices are very heterogeneous in their hardware and software capabilities. They are also subject to complex and live interactions of the system and the user, such as software updates, messaging, and energy-saving. different browsers provide different support of the standard [2,19], that is wide-spread but still evolving.

In a situation that brings a lot of participants to the same physical space, like in a concert, the organisation of sounds in time and space is important. In this paper, among the various sound qualities, we focus on the timing in such a situation. There are different orders of magnitude for accuracy, depending on the usage. For multi-channel rendering, we need to be sample-accurate, which translates to around 20 µs for a common sample-rate. The human threshold of sensitivity is 1 ms for clicks and trained listeners [START_REF] Lunney | Time as heard in speech and music[END_REF]6]. Two coherent speech sounds of the same level appear as echoes when their difference of time is more than 30 ms [1, p. 224], and the accuracy of the violin section of an orchestra is around 40 ms [15, p. 86]. While the sample-accuracy is beyond our reach for now, we aim at the perceptive coherency of distributed sound events. To achieve that, we need synchronisation.

In an orchestra, the conductor provides the synchronisation, while for most specialised audio devices, a cable transmits the word clock. However, mobile browsers can not use a cable, nor a standard facility for a reference time or synchronisation, yet [START_REF]Multi-device Timing Community Group. Multi-device Timing for Web, Community Group Charter[END_REF]. The synchronisation of clocks and devices is not a new problem, and the Network Time Protocol (NTP) [7] is a well-established solution used by millions of servers [START_REF] Mills | Executive Summary: Computer Network Time Synchronization[END_REF]. While it requires a specific server, it has proved to be robust over the years.

Our contribution is based on the HTML5 standard, with a focus on real-time audio rendering, with the Web Audio application programming interface (API). We target any user-agent that supports the standard. Within this context, we propose a pure JavaScript (JS) solution, that runs in any standard browser, or server. We track the timing issues in Section 2, then we propose a synchronisation solution in Section 3, and we evaluate the resulting implementation in Section 4. The relevant source code is libre.1

LATENCY

The devices played the sound with the Web Audio API as soon as possible upon receipt of this message. With both devices at the same distance of the ears (or of the microphones), one could manually adjust the delay of the test device, to try to play simultaneously with the reference device. We experienced a lot of jitter for some devices, especially noticeable for those with a delay over 200 ms: in this case, we selected an approximate mean delay value over time. Figure 1 shows the histogram of these relative delays. While the values are specific to this experiment, they give an order of the magnitude of the problem: around 400 ms of relative time difference across the extrema.2 And, for precise timing, we also need to address the jitter.

Delay (milliseconds)

From our previous example, we track the delays, and note them with arrows on Figure 2. We call host the software that is either a browser or a server, that runs in an operating system (OS), and that allows to run our application code. On the server, we wait until the host schedules our sender's code for execution. Then, we send a message via the Web-Socket API, that goes through the host, the OS, and the hardware, before leaving the server. After the transport, it arrives to the receiver's hardware, OS, and host, before our code is called. Then, the renderer's code schedules a sound via the Web Audio API, to the next audio block. Then the host outputs the sound through the OS, and the hardware. In the air, the transmission delay depends on the distance of the listener.

We split the problem in two parts. From the sender to the receiver, we use a shared synchronised time, in order to compensate the total variable delay (see Section 3); in the renderer, we calibrate and compensate the fixed audio latency (see Section 3.2); and we keep a constant distance from the

SYNCHRONISATION

With a shared reference time, we can compensate any delay from a sender to a receiver, providing that the sender anticipates the total accumulated delay. 3 For example, one can use a look-ahead scheduler [START_REF] Wilson | A Tale of Two Clocks -Scheduling Web Audio with Precision -HTML5 Rocks[END_REF] based on a reference time. It is also possible to use multiple schedulers, all based on the same reference time, even on distributed devices. The question is how to get a shared reference time.

While we follow the same principles as NTP, we do not use it directly for several reasons. First we need a solution that works without a specific server, as our reference possibly comes from a browser. And we adapt the solution to our particular context, Web pages, that need a quick start-up and stabilisation (in seconds, or minutes, instead of hours for NTP). Finally, we integrate all the constraints inherent to the HTML5 environment.

Variable Latency

We follow the principles of NTP [START_REF]How does it work?[END_REF]: in a continuous process, we exchange the times between a client and the reference, we filter the transfers to keep only the quickest ones [START_REF] Mills | Clock Filter Algorithm[END_REF] and we estimate the reference clock, according to a local clock. It is a continuous process, as every clock varies over time.

Clocks

We need a precise reference clock, to get a precise reference time for scheduling audio events. In an HTML5 environment, performance.now is adapted, 4,5 while Date.now should only be used as a last resort. 6Within an AudioContext, it is possible to schedule events according to an absolute currentTime [16] with a resolution of 1 sample. However, as the standard does not requires it to be strictly monotonic, currentTime advances by steps that correspond to the audio block duration. Then, to measure or schedule any event relative to an other time reference like performance.now, or to an external event, its precision is as low as the audio block duration. 7 The mapping of currentTime to performance.now in the standard will hopefully solve this issue for any compliant browser [START_REF] Audio | Need a way to determine AudioContext time of currently audible signal • Issue #12 • WebAudio/web-audio-api[END_REF].

While currentTime is a bad choice as a reference clock, it is a good candidate for a local clock, as we ultimately use it in order to render audio with the Web Audio API. The synchronisation process that we propose does not imply the 3 as there is no way to reduce the intrinsic latency 4 The resolution of performance.now is 1 µs, as it returns a DOMHighResTimeStamp, and it is monotonic. However, "If the User Agent is unable to provide a time value accurate to a thousandth of a millisecond due to hardware or software constraints, the User Agent can represent a DOMHighRes-TimeStamp as a number of milliseconds accurate to a millisecond." [17]. 5 performance.now does not exist for our server that runs Node.js, but we then use process.hrtime, as it is monotonic with a resolution of 1 ns [START_REF] Deveria | Support tables for HTML5[END_REF]. use of the audio clock, 8 but is tolerant to it. Moreover, by directly estimating the reference time from the currentTime, we maximise the resulting audio scheduling accuracy. From now, we focus on the audio clock as the local clock and on performance.now as the reference clock.

Ping-Pong Scheme

The algorithm is developed around a ping-pong scheme, where a client sends a time-stamp tping to a reference, that applies its own time-stamps: Tping on the reception, and Tpong on the emission of its reply. The client then applies a final time-stamp tpong. 9 T is used for reference time, while t is used for local time. Given that both times are expressed with the same unit, this allows the following estimations:

T ping T reference T pong t ping t pong t local
T = T reference = (Tpong + Tping)/2
(1)

t = t local = (tpong + tping)/2 (2) offset = t local -T reference (3) travel duration = tpong -tping -(Tpong -Tping) (4)
This relies on the hypothesis that the network delay is symmetrical, which is never exact, but acceptable when the transmission delay is short, because it bounds the introduced bias. The design of the algorithm favours that.

First, instead of a single ping-pong probe, we send a series of them and we keep only the ones with the shortest travel duration .

To minimise the network congestion, we only send a ping after a pong arrived, or after a time-out. Moreover, the timeout duration increases on any delayed pong (and decreases on arrival, for responsiveness). Finally, there is a random delay in-between the ping-pong series, to spread over time the network usage of the multiple clients.

There is also an implication of our use-case, that brings several mobile devices in the same physical space: we use a wireless local area network (WLAN), for direct connection between devices.

Estimation of the Reference Time

We assume that the reference clock T can be expressed linearly from the local clock t with an offset T0 and a frequency ratio R, like NTP.

T (t) = T0 + R(t -t0) ( 5
)
8 performance.now is a perfectly adapted local clock, too. 9 It is not possible to issue an accurate time-stamp within the browser environment, because it is set in the JS event loop and not by the hardware when it is actually sent or received [9]. Then, the transport duration de facto includes the variable duration between our JS code and the hardware (see Figure 2). Moreover, if we use the low precision audio clock to issue a time-stamp, its precision is also low.

To directly use the audio time, as the local time to synchronise with the reference time, we need to take care about its low precision. To compensate that, the time-span of the observations must we long enough for an accurate estimation of R. On the other hand, it should be short enough to quickly adapt to varying clocks, and to start. One last consideration is that we need enough samples to be able to accurately estimate t0, in order to get a more precise reference than the audio block duration. To mitigate these constraints, we split our synchronisation process in two stages, so as it starts quickly, and it then uses long-term data for better accuracy.

During the training stage, we only adjust the offset of the local clock, after each ping-pong series. We take the mean offset over the 3 quickest travel duration of the last series, to compensate for jitter.

T (t) = t -offset (6)
The heuristic driving the transition to the synchronised stage is that the estimation of the reference clock, that uses R, should be at least as accurate as in the training, despite the errors on R and t0. 10 Then, given a set of measurements (ti, Ti), obtained after the ping-pong series and the filtering, we estimate R with a simple linear regression, which is adapted for a real-time context, as it requires little processing [4].

R = Cov[t, T ] Var[t] = t.T -t.T t 2 -t 2 (7)
While T0 = T and t0 = t are computed at the same time.

As the process is continuous, it is important to monitor it, for reporting purposes, but also to react on unexpected changes. We go back to the training stage any time the estimation of R deviates too much. 11

Fixed Audio Latency

There is no standard way to query the additional latency added after our renderer code (see Figure 2) schedules audio via the Web Audio API, yet [20]. We also measured that guessing the audio block duration is not providing enough information to determine the total added latency. So the only choice for now is to measure it, for any type of device (software and hardware), in order to compensate it later.

We run two audio processes that use a shared synchronised clock. One, that is always the same and that we chose because it is the most stable, serves as a reference. In rendered audio, we measure the difference in time of the device to calibrate from the reference. (See Section 4 for the measurements.)

To get per-device calibration, we store it on the device with localStorage. We also store it on a server, to be able to reproduce a calibration on devices of the same type, with the user-agent 12 as the fuzzy key 13 of the data-base. Of course, this introduces inaccuracy. 10 After measuring devices with a block duration of 5.8 to 85 ms, we chose the following values as a good trade-off between speed, memory, computation, and the necessary data for an accurate estimation: series of 10 ping-pong probes occur every 10 to 15 s; the training lasts for 2 min; the linear regression is computed over a time-span of 15 min, on the quickest travel duration of each series. 11 We use 500 PPM, which is 0.05 %, or the precision of an old mechanical clock [13]. 12 While it is fine for most phones and tablets, it provides no hardware information for the desktop or laptop devices. 13 In order to accommodate to the variations and to still be able to apply the calibration to most devices, we use a Although this works in practice, it is long, error-prone, and an endless effort to integrate new devices and updates, so the integration of such a feature to the standard is eagerly waited.

MEASUREMENTS

On a desktop computer, a Node.js server is running to provide a reference time. It also emits a request each second, for any client to output a click scheduled one second in the future, according to the current reference time. On the same computer, a multi-track recorder records the sound outputs of all the browsers, local or connected via the WLAN.

The time of each measurement starts with the synchronisation processes. In Table 1 we list the devices that we used for this set of measurements. From now on, to refer a particular device type, we only use a distinct letter arbitrarily chosen. Each time the server triggered a click, we make a group by selecting one click of each device. For each group over time, we measure the total time-span, noted range in the figures. We also compute the mean time, the difference of each click from the mean, and their standard deviation, noted stddev. (See Figure 4.)

Device

Homogeneous Devices

For various reasons, some clicks were not rendered by the devices and these are ignored here. Some other clicks rendered too late and they appear as outliers.

We start by measuring 8 local browser windows (type A), that use the same hardware sound interface as the multi-track recorder, so they all share the same audio clock. In Figure 5, we observe that even during the training stage, the accuracy is better than the audio block duration, mainly because of Levenshtein distance, which is the sum of added and removed characters. the mean offset over 3 values. 14 After quick stabilisation, the accuracy is always better than 0.8 ms. This confirms that the reference time is precise, and its estimation correct.

One of these windows serves as the audio reference process in Section 4.2.

Time (minutes:seconds) 0:00 1:00 2:00 3:00 4:00 5:00 6:00 7:00 8:00

Standard deviation (milliseconds) -Range (milliseconds) Then we measure 8 mobile devices (type B), that use the WLAN, and their own local clock. In Figure 6, we observe that after 2 min the devices start the estimation of the reference clock's frequency. These estimations get better and better over time, as the local drift (seen as the local slope) progressively diminishes. We also note that the local drifts do not imply a loss of accuracy comparing to the training stage. The synchronisation process is stable and the most accurate after 15 min, 15 and the range is approximately equals to the audio block duration, while the standard deviation is onethird of it.

Time (minutes:seconds) 0:00 3:00 6:00 9:00 12:00 15:00 18:00 21:00 24:00 27:00 30:00

Standard deviation (milliseconds) -Range (milliseconds) Then, we measure that the accuracy is not directly bounded by the audio block duration, by measuring 8 devices of type C, with a long block (85 ms). In Figure 7, after stabilisation, the range is approximately one-quarter of the audio block duration, while the standard deviation is around one tenth of it. 2 clicks rendered too late, at 10 and 29 min.

On this long-term observation, we note a discontinuity around 19 min: by looking at the individual recordings and after investigation, we found out that there is a discontinuity in the audio rendering, and time. This seems to sporadically happen on all of the mobile devices that we studied (one device at a time). While the synchronisation process recovers from it, this is still bad for audio rendering. We did not experience such a problem on desktop or laptop devices.

Heterogeneous Devices

To measure heterogeneous devices, we use a local browser as a reference (of type A, as in Figure 5), that always stays synchronised to our reference clock. After the synchronisation of the different devices, we calibrate their relative delays, in order to compensate them during the next measurement. All devices of the same type share the same calibration. Then, we restart the synchronisation process to measure it (except for the reference). The analysis of the data is the same as before for the range, but we measure the difference of each device from the reference, for each click, and we compute the standard deviation from it (see Figure 8).

We mix up devices of type B and of type C, and we measure them with a reference of type A, to check that we obtain the same results as before, with only devices of type C (see Figure 7). Looking at the individual delays from the reference, we confirm that the the overall accuracy is bounded by the less accurate devices, of type C. We note that the different types exhibit different long-term patterns.

Time (minutes:seconds) 0:00 3:00 6:00 9:00 12:00 15:00 18:00 21:00 24:00 27:00 30:00 33:00 Then, with the same reference of type A, we measured 7 other devices, of various platforms and characteristics, with an audio block duration ranging from 2.9 to 93 ms. In Figure 9, we observe that during the training the range is under 30 ms, while in the long term it oscillates between 5 and 10 ms, with a standard deviation between 1 and 3 ms. Time (minutes:seconds) 0:00 3:00 6:00 9:00 12:00 15:00 18:00 21:00 24:00 27:00 30:00 33:00 Delay from reference (milliseconds) Looking at the individual delays, in Figure 10, we note that the very accurate value around 16 min is an effect of the individual long-term oscillations. While some devices are more accurate, all of them are accurate by 5 ms around the reference after stabilisation. They exhibit various long-term patterns, but all of their local discontinuities is under 2 ms.

CONCLUSIONS

We showed that it is already possible to use heterogeneous devices for distributed audio rendering, providing they support standard HTML5 browsers, despite their differences. The requirement on the reference is very light, as it only needs to be able to answer to a ping, so it runs on any standard browser, or server.

We developed a synchronisation solution that is valid for the rendering of audio events, by sharing a reference time, with an individual accuracy of 1 to 10 ms, 20 ms in range, and 0.2 to 5 ms in standard deviation, for all the devices that we measured. This is below their audio block duration.

We successfully used it for a number of realisations, including a distributed loop sequencer, a distributed reverberation processor, and individual instruments sharing a common musical time.

However, some late scheduling may happen, due to network, computation, or unrelated causes on the device. Moreover, we will need to investigate the discontinuities that seem to happen sometimes in the Web Audio rendering on all mobile devices.

As the standard is evolving, it will hopefully solve the calibration step by allowing to directly query the latency added after the Web Audio currentTime. And the overall accuracy will improve with a native correspondence between performance.now and currentTime.

  Finally, the Licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0). Attribution: owner/author(s). Web Audio Conference WAC-2016, April 4-6, 2016, Atlanta, USA.

  c 2016 Copyright held by the owner/author(s).

Figure 1 :

 1 Figure 1: Histogram of relative overall delays (including network and audio) of various devices. Android 4.1, 4.2, 4.3, 4.4, 5.0; FirefoxOS 2.1; iOS 7, 8.

Figure 2 :

 2 Figure 2: Accumulation of multiple delays from a remote sender to a listener.

Figure 3 :

 3 Figure 3: Exchange of time-stamps during a pingpong round-trip.

Figure 4 :

 4 Figure 4: Mean, range, and standard deviation of clicks within a group.

Figure 5 :

 5 Figure 5: Synchronisation of 8 browser windows on a single desktop computer (type A), also running the server, and the recorder. 11.6 ms audio block.

Figure 6 :

 6 Figure 6: Beginning of synchronisation of 8 devices of type B. 5.8 ms audio block.

Figure 7 :

 7 Figure 7: Synchronisation of 8 devices of type C, over long-term. 85 ms audio block.

Figure 8 :

 8 Figure 8: Range of clicks within a group, and standard deviation from reference.

Figure 9 :

 9 Figure 9: Synchronisation of 7 heterogeneous devices. Standard deviation from reference (type A). 2.9 to 93 ms audio block, 0 to 398 ms calibration.

Figure 10 :

 10 Figure 10: Synchronisation of 7 heterogeneous devices. Individual delays from reference (type A). 2.9 to 93 ms audio block, 0 to 398 ms calibration.

Table 1 : Devices used for measurements.

 1

		OS	Browser
	Galaxy A3 (mobile)	Android 5.0.2 Chrome 45
	Galaxy S3 Mini (mobile) Android 4.2.2 Chrome 44
	iMac (desktop)	OS X 10.9.5	Chrome 45
	iPad Mini 3 (mobile)	iOS 9.0.2	Safari 9
	iPhone 4 (mobile)	iOS 7.1.2	Safari 7
	iPod touch 5 (mobile)	iOS 8.4.1	Safari 8
	MacBook Pro (laptop)	OS X 10.9.5	Firefox 41
	Nexus 4 (mobile)	Android 5.1.1 Chrome 45
	StarAddict III (mobile)	Android 4.2.2 Chrome 39
	XPS 12 (laptop)	Windows 10.0 Edge 12

The source code used for clock synchronisation is published at https://github.com/collective-soundworks/ sync/, and the source code used for device calibration and measurements is published at https://github.com/ collective-soundworks/soundworks-calibration/.

It is a lot: in the air, sound travels 130 m during this time.audio output, or we use a cable, to ignore the position of the listener.

Date.now resolution is 1 ms [3], and it is not monotonic, as it follows the OS time, with its adjustments.

While the audio block duration is not directly available in HTML5, we measured it by requesting a series of time and by looking at the advances. We measured values from 2.9 to

We tried removing it. See Section 3.1.3

ACKNOWLEDGEMENTS

We conducted this work in the context of the CoSiMa project, which is supported by the French National Research Agency (http://cosima.ircam.fr/, ANR-13-CORD-0010). The authors warmly thank their colleagues Olivier Warusfel, Benjamin Matuszewski, and Samuel Goldszmidt, for their precious contributions, and all the people who let us use their personal device.