Thomas Bonald
email: thomas.bonald@telecom-paristech.fr

Luca Muscariello
email: luca.muscariello@orange-ftgroup.com

Norberto Ostallo
email: norberto.ostallo@gmail.com

Self-Prioritization of Audio and Video Traffic

We present a packet scheduler called "shortest queue first" (SQF) that aims at protecting audio and video traffic from the congestion caused by data traffic. Unlike standard solutions, the services to be handled with priority are not known in advance. It is rather the traffic characteristics of audio and video applications that are used to detect their delay sensitivity. The SQF algorithm does not require any prior configuration of the network and, as such, adapts to the fast evolution of traffic and usage. The performance of the proposed solution is demonstrated using both analysis and experiments on a testbed emulating a residential access line.

I. INTRODUCTION

We have faced a dramatic increase of video traffic in the last decade, exemplified by the popularity of video file sharing systems and the advent of TV over IP. This fast growth is expected to continue within the next few years, sustained by the development of video-on-demand services, catch-up TV, and P2P streaming applications. Such delay-sensitive services often suffer from the congestion caused by data traffic, especially on the 'last mile", namely the user's access line and possibly the first aggregation links of the backhaul network, as illustrated by Fig. 1. In this paper we focus on streaming applications that require expedited packet forwarding like interactive communications (video-conferencing, VOIP) or Web-TV. Many other streaming applications, less sensitive to timely delivery, frequently make use of progressive downloads (VoD, YouTube, Daily Motions etc.) and are more robust to packet delays and losses at the cost of larger play-out delays. In this paper we do not consider such applications that rather require a minimum available bandwidth to the source, than expedited packet forwarding. The current solution proposed by IETF and implemented by most suppliers relies on the Diffserv architecture [START_REF] Blake | Architecture for Differentiated Service, RFC 2475[END_REF]. Packets are marked at the network edge according to some pre-defined policy and handled with high or low priority in the network depending on their mark. This architecture is used by ISPs to protect their own telephony and video services for instance. It is hardly applicable to tier-services, however, that appear and evolve very rapidly according to the users' needs and the business opportunities. Changing the marking policy at this pace is usually considered as either infeasible or economically nonviable.

We propose a packet scheduler called "shortest queue first" (SQF) that introduces implicit service differentiation. The services to be handled with priority are not known in advance. It is rather the characteristics of audio and video applications, namely the fact that packet arrivals are regulated by some source codec and not by the congestion control mechanisms of TCP, that are used to detect their delay sensitivity. Note in particular that SQF equally applies to audio and video traffic over UDP and TCP, the congestion control mechanisms of TCP being typically inactive in the latter case (they become active only if packets queue in the network, which is precisely what SQF aims at avoiding). The algorithm does not require any prior configuration of the network and, as such, adapts to the fast evolution of traffic and usage.

The rest of the paper is organized as follows. Some related work is presented in the next section. The SQF algorithm is described in Section III. Sections IV and V give the performance results, obtained both by analysis and experiments on a testbed, when the SQF algorithm is activated on the user's access line. Section VI concludes the paper.

II. RELATED WORK

The SQF algorithm is somewhat related to fair queuing (FQ), a scheduling policy introduced by Nagle [START_REF] Nagle | On Packet Switches with Infinite Storage[END_REF] as a means to protect TCP flows from non-responsive, UDP flows. Shreedhar and Varghese proposed an efficient implementation of FQ through the deficit round-robin (DRR) algorithm [START_REF] Shreedhar | Efficient fair queueing using deficit round robin[END_REF]. Some authors observed that FQ is not only desirable for fairness but also for the packet delay of those flows that use less than their fair share, see [START_REF] Demers | Analysis and simulation of a fair queueing algorithm[END_REF], [START_REF] Suter | Design considerations for supporting TCP with per-flow queueing[END_REF]. This idea is exploited by Kortebi, Oueslati and Roberts, who first coined the term of "implicit" service differentiation [START_REF] Kortebi | Cross-protect: implicit service differentiation and admission control[END_REF]: their priority fair queuing (PFQ) algorithm gives strict priority to the packets of non-backlogged flows, which minimizes their packet delay; backlogged flows are scheduled according to the standard FQ policy.

Unlike FQ and PFQ, SQF is not based on the throughput of active flows but only on the number of packets they have in the buffer. Specifically, SQF always serves a packet of that flow having the smallest amount of data in the buffer, hence the name. It is thus the traffic characteristics of audio and video flows, and in particular the fact that packet arrivals are regulated by the source codec, that are used to schedule them with high priority. In particular, SQF is able to prioritize audio and video traffic of high rates, close to the link capacity.

In [START_REF] Carofiglio | On the impact of TCP and per-flow scheduling on Internet performance[END_REF], SQF has been analyzed in a link fed by multiple TCP sources, through fluid differential equations. In addition, the performance of CBR sources in presence of TCP traffic has been considered. A main limitation of fluid modeling is that packet fluctuations are neglected, and does allow to extend the analysis in [START_REF] Carofiglio | On the impact of TCP and per-flow scheduling on Internet performance[END_REF] to a larger class of sources.

In this paper we further analyze SQF, considering packet fluctuations to highlight some properties of the scheduler that cannot be measured using fluid modeling. We here present both analytical and experimental results comparing the performance of SQF and FQ in the more realistic context of VBR (variable bit rate) traffic.

The efficiency of SQF has also be demonstrated in [START_REF] Bonald | Shortest queue first: implicit service differentiation through per-flow scheduling[END_REF] on the Livebox, an ADSL router available to customers of Orange's Broadband services 1 .

It is worth observing that SQF is the exact opposite of the "longest queue first" (LQF) policy considered for instance by Dimakis and Walrand [START_REF] Dimakis | Sufficient conditions for stability of longestqueue-first scheduling: second-order properties using fluid limits[END_REF] as an approximate, distributed implementation of the maximal weight matching algorithm of Tassiulas and Ephremides [START_REF] Tassiulas | Stability properties of constrained queueing systems and scheduling for maximum throughput in multihop radio networks[END_REF]. These scheduling policies aim at maximizing the utilization of some interferring resources in the context of wireless networks [START_REF] Sharma | Joint Congestion Control and Distributed Scheduling for Throughput Guarantees inWireless Networks[END_REF] or packet switches [START_REF] Mckeown | Achieving 100% throughput in an input-queued switch[END_REF] for instance. Our problem is very different: we focus on a single resource (e.g. the user's access line) and seek to optimize the multiplexing of different services (audio, video and data).

Finally, the drop policy plays a critical role in bandwidth sharing. Some proposals use FIFO scheduling and thus rely entirely on the buffer management to enforce fairness, see [START_REF] Pan | CHOKe: A stateless queue management scheme for approximating fair bandwdith allocation[END_REF], [START_REF] Pan | Approximate fairness through differential dropping[END_REF]. As pointed out by Suter et. al. [START_REF] Suter | Design considerations for supporting TCP with per-flow queueing[END_REF], FQ must also be combined with the Longest Queue Drop (LQD) policy to protect flows of low throughput. Similarly, we apply LQD to protect regulated flows: the combination of SQF and LQD guarantees both low delays and low loss rates to audio and video traffic, as shown in the rest of the paper.

III. SHORTEST QUEUE FIRST

A. Flow identification

Like FQ and PFQ, the SQF algorithm is "flow-aware": each packet is dropped or served depending on the flow it belongs to. For present purposes, we refer to a flow as the set of packets that belong to the same instance of application. In practice, a flow is identified either through the 5-tuple of the 1 http://en.wikipedia.org/wiki/Orange_Livebox IP header, or through some pre-defined part of it. The exact definition depends on the desired degree of traffic aggregation. On the upstream of the user's access line for instance, that is in the equipment connecting the user to the network, it may be beneficial to consider the source port as the flow identifier so as to aggregate all packets of the same application, whatever the destination of these packets. All packets sent to the various peers of a P2P file swarm are then considered as belonging to the same flow, for instance.

B. Packet scheduler

A flow is said to be active if it has at least one packet in the buffer. The packet scheduler maintains one virtual queue per active flow and always serves a packet from the shortest queue in bytes. It is thus the volume of data of each flow that is used to select the shortest queue, making the algorithm insensitive to the packet size distribution. The algorithm is work-conserving and non-preemptive. Note that the number of active flows is upper bounded by the buffer size, which makes the scheduler perfectly scalable. As mentioned above, the SQF algorithm is combined with LQD so that regulated flows (with low virtual queues) do not suffer any packet drop, as illustrated by Fig. 2 and the above pseudo-code. The total buffer is then simply sized so as to ensure an efficient utilization by TCP; typical values range from 50 to 200 MTU sized packets, see [START_REF] Raina | Part II: Control theory for buffer sizing[END_REF].

IV. ANALYTICAL RESULTS

This section is devoted to the performance analysis of SQF. Specifically, we assess the robustness of SQF to the jitter of one or several VBR video flows in the presence of data traffic, for which the considered link is assumed to be the bottleneck.

A. A single video stream

We first consider a single video stream that competes for bandwidth with n TCP flows. We assume that these TCP flows saturate the buffer and have approximately the same number of packets in it. For simplicity, we also assume that all video packets have the same size, taken as the data unit.

Let x be the number of video packets in the buffer. Denoting by B the buffer size, the volume available for each TCP flow is given by: B -x n .

The video stream has priority as long as it has a lower data volume in the buffer than each TCP flow, that is if:

x < B n + 1 . ( 1
)
Let C be the link capacity in packet/s. If the video stream were purely CBR (constant bit rate) at rate λ < C, there would be at most one packet in the buffer and the video stream would always be prioritized. More generally, if the video stream is VBR but has a strictly enforced peak rate λ < C, there is at most one packet in the buffer and the video stream is always prioritized. Now assume that the peak rate λ is not strictly enforced. Specifically, we assume that packets arrive according to a Poisson process of intensity λ. Thus, while the theoretical peak rate is equal to λ, the actual peak rate is infinite (there is no lower bound on the packet inter-arrival time). Note that this traffic model with transmission at the theoretical peak rate λ is in fact much more pessimistic than any more realistic, long-range dependent traffic model that accounts for the rate fluctuations between 0 and λ due to the structure of the video [START_REF] Beran | Long-range dependence in variable-bit-rate video traffic[END_REF].

We seek to estimate the probability p(T ) that the video is de-prioritized, in the sense that condition (1) is violated, over some time period of length T . In view of the above assumptions, this reduces to the analysis of the transient behavior of an M/D/1 queue. In order to get simple and explicit results, we first calculate the probability q(t) that the number of arrivals exceeds the service capacity plus the buffering capacity (1) over any time interval of length t:

q(t) = Pr N (t) ≥ Ct + B n + 1
where N (t) denotes a Poisson random variable of mean λt. We then divide the time period T into k intervals of length T /k and calculate the probability q k that the number of arrivals exceeds the service capacity plus the buffering capacity (1) on at least one of these intervals:

q k = 1 -1 -q T k k .
The probability of de-prioritization p(T ) is then estimated as the maximum of the probabilities q k over all k:

p(T ) = max k≥1 q k . (2)
Note that the maximum is reached for some finite k since q k tends to 0 as k grows to infinity. Fig. 3 gives the probability of de-prioritization as a function of the video peak rate λ for a 10-min video on a 10Mbit/s link with different numbers n of competing TCP flows. The buffer size is equal to 200 packets, with a packet size of 1250B. For n = 20 competing flows for instance, the probability of deprioritization is close to 0 as long as the video peak rate is less than 6Mbit/s. The figure also shows the probability of deprioritization under FQ, which is equal to 0 if λ < C/(n + 1) (since the video peak rate is less than the fair share) and to 1 otherwise. For n = 20 competing flows for instance, the video peak rate cannot exceed 480kbit/s. Another way of evaluating the performance of SQF is to estimate the average time T during which the video is prioritized. Note that the probability that the time of prioritization is larger than t is equal to 1 -p(t), where p(t) is given by (2). We deduce:

T = ∞ 0 (1 -p(t))dt.
Fig. 4 gives the average time of prioritization T as a function of the video peak rate λ on a 10Mbit/s link with different numbers n of competing TCP flows. For n = 20 competing flows for instance, this average time is larger than 180min as long as the video peak rate is less than 6Mbit/s. Under FQ, the video peak rate cannot exceed 480kbit/s in this case.

B. Multiple video streams

The results readily extend to an arbitrary number m of video streams. Let x i be the number of packets of video stream i in the buffer. Let x = m i=1 x i . All video streams have priority as long as each has a lower data volume in the buffer than each TCP flow, that is if:

∀i, x i < B -x n .
(3) Clearly, the condition (1) imposed on the total number of video packets is sufficient. This is equivalent to consider the m video streams of rate λ as a single video stream of rate mλ. Thus for a 10Mbit/s link with n = 20 competing TCP flows, SQF gives priority to m = 3 video streams of peak rate 2Mbit/s (since the total video stream does not exceed 6 Mbit/s).

V. EXPERIMENTAL RESULTS

This section presents some experimental results on the performance of FIFO, FQ and SQF. We present here a limited number of tests for lack of space and for sake of clarity. The set of test has been chosen in order to better expose the behavior and performance of the schedulers in presence of more realistic traffic patterns.

A. Test-bed setup

The test-bed consists of four Linux PCs, that emulate a router, two servers and a client, as depicted by Fig. 5. One server is an Apache Web server [2], the other one is a video streaming server using VLC [3]. The Linux router is equipped with three network Ethernet cards so as to connect the two servers and the client in a star topology, using standard Linux tools [START_REF]Linux advanced routing and traffic control[END_REF]. All line cards are used at 100Mbit/s except for the link of the client that is used at 10Mbit/s and plays the role of the user's access line. The corresponding output line card of the router has a buffer size of 50 MTU sized packets (with a MTU of 1500B) and embeds one egress queuing discipline, chosen among FIFO (without buffer management), FQ (DRR algorithm with LQD), and SQF (as described in Sec. III). Flows are identified through the 5-tuple of the IP header.

B. Traffic scenario

The client downloads several files from the Web server while watching a video channel streamed on RTP over UDP by the VLC server. The video is composed of two flows, one for the video and one for the audio, on different UDP ports. The codec is MPEG2 for both video and audio. The video stream is a VBR flow with an average rate of 5Mbit/s while the audio stream is a VBR flow with an average rate of 64kbit/s.

C. Quality of the video stream

The quality of the video stream is estimated through the loss rate and jitter experienced by packets of the audio and video flows on a 10-min sequence. These performance metrics are calculated from tcpdump records [4], available at the client input interface. The loss rate is deduced from the stream sequence numbers while jitter is estimated through the interpacket delay variation, as defined in [START_REF] Demichelis | IP Packet Delay Variation Metric for IP Performance Metrics[END_REF].

Fig. 6 shows the packet loss rate of the audio and video flows with respect to the number n of competing file downloads, varying from 1 to 20. We observe that the loss rate is negligible under SQF independently of n, as expected in view of the analysis of Sec. IV, whereas it is much too high under FIFO and FQ as soon as n > 1. Under FIFO, the packet loss rate of the audio flow grows linearly from 1% to more than 25% as n grows from 1 to 20; it is slightly less for the video flow. Video traffic having a higher rate than audio forces TCP to back-off and reduce data sending rate.

Under FQ, the behaviors of the audio and video flows differ significantly: the audio flow has an average rate of 64kbit/s that is less than the fair share, which explains the resulting low loss rate; the video flow, on the other hand, has an average rate of 5Mbit/s that is larger than the fair share as soon as n > 1, which explains the resulting high loss rate. These results confirm the poor performance of FQ under high data traffic load.

The results are in agreement with those obtained for the jitter, reported in Fig. 7. We observe that under FQ, the jitter increases with the number of flows for both the audio flow and the video flow, due to the round robin scheduling time. PFQ would limit the jitter suffered by the audio flow but not that of the video flow, whose average rate is larger than the fair share as soon as n > 1. SQF turns out to be beneficial for both audio and video, independently of the number of competing file downloads.

D. Data traffic

In Tab.I we have reported some performance measures for data traffic. The data bandwidth share corresponds to the total throughput of data traffic while Jain's index indicates how this bandwidth is distributed among the n data transfers. Specifically, Jain's index is defined by:

J = ( n i=1 y i ) 2 n n i=1 y 2 i
where y i denotes the normalized throughput achieved by the i-th data download at the end of the experiment. Note that J varies from 1/n for a totally unfair sharing (a single flow gets all the resource) to 1 for a perfectly fair sharing (all throughputs are equal).

As expected, the data bandwidth share increases with n under both FIFO and FQ whereas it remains constant under SQF, due to the self-prioritization of the video stream. Under FQ, the bandwidth available for the video stream is not sufficient as soon as n > 1, which is in agreement with the results of Sec. V-C. Note that in all cases, the overall utilization does not reach 100% due to the transmission of duplicate packets by TCP. Under SQF for instance, the data bandwidth

E. Impact of video rate variability

We have so far assumed that the video stream does not suffer any variable delay on its path from the video server to the considered bottleneck link. In order to illustrate the impact of jitter on SQF efficiency, we add artificial packet delays at the video source. Specifically, packets are delayed according to a Gaussian random variable with different values of the standard deviation δ, so that packets may be sent in bursts similarly to those generated by TCP.

We report in Fig. 8 the loss rate experienced by the video stream with respect to the standard deviation δ, for a link capacity of 10Mbit/s and 100Mbit/s under SQF. When δ increases, packets are more likely to be sent in bursts and to accumulate in the buffer, causing the de-prioritization of the video stream. For a 10Mbit/s link for instance, the video stream is de-prioritized when δ ≥ 5ms; this threshold value is larger for a 100Mbit/s link.

VI. CONCLUSION

We have presented a packet scheduler that automatically prioritizes audio and video traffic for interactive applications. The algorithm need not any prior information about the services to prioritize unlike the Diffserv architecture. It simply relies on the following key difference between streaming and data traffic: while the former generates no or little queuing as long as the stream rate, controlled by the codec, is less than the bottleneck capacity, the latter tends to fully exploit the available bandwidth and thus to saturate the buffer of the bottleneck link. This difference is easily detected by the SQF algorithm. By contrast, the FQ scheduling policy is based on the throughput of each flow and thus is unable to prioritize a video stream in the presence of high data traffic load.

We claim that FQ should rather be used to fairly share resources among multiple users, in back-haul or passive optical networks for instance. Note the high bandwidth of the corresponding links could well be saturated. The advent of optical Internet access will likely drive a different domestic usage with richer multimedia content, a significant part of this content being produced by the users themselves and stored remotely into virtualized servers. Both the uplink and the downlink will then be shared by a number of applications, both streaming and elastic, whose multiplexing will be critical. SQF could then be used to self-prioritize delay-sensitive services within each user's bandwidth share. Note, again, that the scalability of the algorithm is guaranteed by the limit on the number of active flows imposed by the buffer size. Moreover, this number has been proved to be typically limited by the nature of traffic itself, independently of the link capacity, see [START_REF] Kortebi | On the Scalability of Fair Queueing[END_REF], [START_REF] Kortebi | Evaluating the number of active flows in a scheduler realizing fair statistical bandwidth sharing[END_REF], [START_REF] Kortebi | Minimizing the overhead in implementing flow-aware networking[END_REF]. For future work, we plan to assess the efficiency and robustness of the envisaged hierarchical scheduling policy consisting of FQ at user level and SQF at flow level.

Fig. 1 .

 1 Fig. 1. Congestion on the network's last mile.

  Fig. 2. Shortest Queue First.

Fig. 3 .

 3 Fig. 3. Probability of de-prioritization for a 10 min video on a 10Mbit/s link with n = 5, 10, 20 competing TCP flows (from right to left).

Fig. 4 .

 4 Fig. 4. Average time of prioritization of a video on a 10Mbit/s link with n = 5, 10, 20 competing TCP flows (from right to left).

Fig. 5 .

 5 Fig. 5. Testbed set-up made of two servers and one client connected in a star topology.

Fig. 6 .

 6 Fig. 6. Packet loss rate of the audio and video flows with respect to data traffic load.

Fig. 7 .

 7 Fig. 7. Jitter of the audio and video flows with respect to data traffic load.

Fig. 8 .

 8 Fig. 8. Packet loss rate of the video flow with respect to the packet interdeparture time standard deviation.

TABLE I DATA

 I BANDWIDTH SHARE (IN MBIT/S) AND JAIN'S INDEX FAIRNESS AS A FUNCTION OF THE NUMBER n OF DATA DOWNLOADS.

	n	1	5	10	15	20
	FIFO 4.1/0.95 4.4/0.91	4.8/0.95 5.1/0.95 5.6/0.99
	FQ	4.1/0.99 7.5/0.99	8.5/0.95 8.9/0.99 9.1/0.99
	SQF	4.1/0.95 4.1/0.90	4.1/0.91 4.1/0.95 4.1/0.95
	share is equal to 4.1Mbit/s so that the overall utilization,
	including the 5Mbit/s video flow and the 64kbit/s audio flow,
	is approximately equal to 92%. Finally, fairness as measured
	by Jain's index is excellent for all schedulers.

ACKNOWLEDGMENT

This work has been funded by the EU FP7 4WARD project on the Future Internet.


Sajith Kalathingal

Sylvain Collange

Bharath N Swamy

André Seznec

Transforming TLP into DLP with the Dynamic Inter-Thread Vectorization Architecture

Keywords: Simultaneous MultiThreading, Single instruction multiple data, Single program multiple data, Vectorization SMT, SIMD, SPMD, vectorisation

Threads of Single-Program Multiple-Data (SPMD) applications often execute the same instructions on different data. We propose the Dynamic Inter-Thread Vectorization Architecture (DITVA) to leverage this implicit Data Level Parallelism in SPMD applications to create dynamic vector instructions at runtime. DITVA extends an SIMD-enabled in-order SMT processor with an inter-thread vectorization execution mode. In this mode, identical instructions of several threads running in lockstep are aggregated into a single SIMD instruction. DITVA leverages existing SIMD units, balances TLP and DLP with a warp/thread hierarchy, and maintains binary compatibility with existing CPU architectures.

Introduction

Single-Program Multiple-Data (SPMD) applications express parallelism by creating multiple instruction streams executed by threads running the same program but operating on different data. The underlying execution model for SPMD programs is the Multiple Instruction, Multiple Data execution model, i.e., threads execute independently between two synchronization points. The SPMD programming model often leads threads to execute very similar control flows, i.e., often executing the same instructions on different data. The implicit data level parallelism (DLP) that exists across the threads of an SPMD program is neither captured by the programming model -thread execution can be asynchronous -nor leveraged by current processors.

Simultaneous Multi-Threaded (SMT) processors [START_REF] Tullsen | Simultaneous multithreading: Maximizing on-chip parallelism[END_REF][START_REF] Dean M Tullsen | Exploiting choice: Instruction fetch and issue on an implementable simultaneous multithreading processor[END_REF] were introduced to leverage multiissue superscalar processors on parallel or multi-program workloads to achieve high single-core throughput whenever the workload features parallelism or concurrency. SMT cores are the building bricks of many commercial multi-cores including all the recent Intel and IBM high-end multi-cores. While SMT cores often exploit explicit DLP through Single Instruction, Multiple Data (SIMD) instructions, they do not leverage the implicit DLP present in SPMD applications.

In this paper, we propose the Dynamic Inter-Thread Vectorization Architecture (DITVA) to exploit the implicit DLP in SPMD applications dynamically at a moderate hardware cost. DITVA extends an in-order SMT architecture [START_REF] Tullsen | Simultaneous multithreading: Maximizing on-chip parallelism[END_REF] with a dynamic vector execution mode supported by SIMD units. Whenever possible DITVA executes the same instruction for different threads running in lockstep on replicated functional units. At runtime, DITVA synchronizes threads within groups, or warps, to uncover the hidden DLP. Dynamic vectorization does not require additional programmer effort or algorithm changes to the existing SPMD applications. DITVA even preserves binary compatibility with the existing general purpose CPU architectures as it does not require any modification in the ISA.

Our experiments on SPMD applications from the PARSEC and SPLASH benchmarks [START_REF] Bienia | The parsec benchmark suite: Characterization and architectural implications[END_REF][START_REF]Splash-2[END_REF] show that the number of instructions fetched and decoded can be reduced, on average, by 40% on a 4-warp × 4-thread DITVA architecture compared with a 4-thread SMT. Coupled with a realistic memory hierarchy, this translates into a speed-up of 1.44× over 4-thread in-order SMT, a very significant performance gain. DITVA provides these benefits at a limited hardware complexity since it relies essentially on the same control hardware as the SMT processor and the replication of the functional units by using SIMD units in place of scalar units. Since DITVA can leverage preexisting SIMD execution units, this benefit is achieved with 22% average energy reduction. Therefore, DITVA appears as a very energy-effective design to execute SPMD applications.

The remainder of the paper is organized as follows. Section 2 motivates the DITVA proposition for a high throughput SPMD oriented processor architecture. Section 3 reviews some related works. Section 4 describes our proposed DITVA architecture. Section 5 presents our experimental framework and the performance and design tradeoffs of DITVA. Section 6 describes the implications of DITVA on hardware complexity and does power consumption analysis. Finally, Section 7 concludes this study and introduces directions for future works.

Motivation

In this section, we first motivate our choice of building an SPMD oriented throughput processor on top of an in-order SMT processor. Then we argue that SPMD programs offer tremendous opportunities to mutualize a significant part of the instruction execution of the different threads.

SMT architectures

SMT architectures [START_REF] Tullsen | Simultaneous multithreading: Maximizing on-chip parallelism[END_REF] were introduced to exploit thread-level and/or multi-program level parallelism to optimize the throughput of a superscalar core. Typically, on an SMT processor, instructions from the different hardware threads progress concurrently in all stages of the pipeline. Depending on the precise implementation, some pipeline stages only treat instructions from a single thread at a given cycle. For instance the instruction fetch pipeline stage [START_REF] Seznec | Design tradeoffs for the alpha EV8 conditional branch predictor[END_REF], while some other pipeline stages like the execution stage, mix instructions from all threads.

SMT architectures aim at delivering throughput for any mix of threads without differentiating threads of a single parallel application from threads of a multi-program workload. Therefore, when threads from an SPMD application exhibit very similar control flows, SMT architectures only benefit from these similarities by side-effects of sharing structures such as caches or branch predictors [START_REF] Hily | Branch prediction and simultaneous multithreading[END_REF].

SMT architectures have often been targeting both high single-thread performance and high parallel or multi-program performance. As a consequence, most commercial designs have been implemented with out-of-order execution. However in the context of parallel applications, outof-order execution may not be cost effective. An in-order 4-thread SMT 4-issue processor have been shown to reach 85 % of the performance of an out-of-order 4-thread SMT 4-issue processor [START_REF] Hily | Out-of-order execution may not be cost-effective on processors featuring simultaneous multithreading[END_REF]. Therefore, in-order SMT appears as a good architecture tradeoff for implementing the cores of an SPMD oriented throughput processor.

Instruction redundancy in SPMD threads

In SPMD applications, threads usually execute very similar flows of instructions. They exhibit some control flow divergence due to branches, but generally a rapid reconvergence of the control flows occur. To illustrate this convergence/divergence scenario among the parallel sections, we display a control flow diagram from the Blackscholes workload [START_REF] Bienia | The parsec benchmark suite: Characterization and architectural implications[END_REF] in figure 1. All the threads execute the convergent blocks while only some threads execute the divergent blocks. Moreover, in the case of divergent blocks, more than one thread often executes the divergent block.

Also, SPMD applications typically resort to explicit synchronization barriers at certain execution points to enforce dependencies between tasks. Such barriers are natural control flow reconvergence points. On a multi-threaded machine, e.g. an SMT processor, threads execute independently between barriers without any instruction level synchronization favoring latency hiding and avoiding starvation. On an SMT processor, each thread manages its own control flow. In the example Inria illustrated above, for each convergent block, instructions are fetched, decoded, etc. by each of the thread without any mutualization of this redundant effort. The same applies to the divergent blocks that are executed by more than one thread. This appears as a large waste of resources. Indeed, a prior study on the PARSEC benchmarks have shown that the instruction fetch of 10 threads out of 16 on average could be mutualized if the threads were synchronized to progress in lockstep [START_REF] Milanez | Thread scheduling and memory coalescing for dynamic vectorization of SPMD workloads[END_REF].

The DITVA architecture leverages this instruction redundancy to mutualize the front-end pipeline of an in-order SMT processor, as a resource-efficient way to improve throughput on SPMD applications.

Related works

DITVA aims at exploiting data-level parallelism in SPMD applications by extending an inorder SMT processor. Therefore, DITVA is strongly related to the three domains, SIMD/vector architecture, SIMT also known as GPU architectures and SMT architectures.

SIMD and/or vectors

Static DLP, detected on the source code, has been exploited by hardware and compilers for decades. SIMD and/or vector execution have been considered as early as the 1970s till the 1990s in vector supercomputers [START_REF] Russell | The cray-1 computer system[END_REF]. Performance on these systems was highly dependent on the ability of application programmers to express computations as operations on contiguous, strided or scatter/gather vectors and on the ability of compilers to detect and use these vectors [START_REF] Padua | Advanced compiler optimizations for supercomputers[END_REF]. In the mid-1990s, SIMD instructions were introduced in the microprocessor ISAs, first to deal with multimedia applications [START_REF] Lee | Multimedia extensions for general-purpose processors[END_REF] e.g. VIS for the SPARC ISA or MMX for x86. More recently ISAs have been augmented with SIMD instructions addressing scientific computing, e.g. SSE and AVX for x86_64.

However, SIMD instructions are not always the practical vehicle to express and exploit possible DLP in all programs. In many cases, compilers fail to vectorize loop nests with independent loop iterations that have potential control flow divergence or irregular memory accesses. One experimental study [START_REF] Maleki | An evaluation of vectorizing compilers[END_REF] shows that only 45-71% of the vectorizable code in Test Suite for Vectorizing Compilers (TSVC) and 18-30% in Petascale Application Collaboration Teams (PACT) and Media Bench II was vectorized by auto-vectorization of ICC, GCC and XLC compilers because of inaccurate analysis and transformations.

Also, the effective parallelism exploited through SIMD instructions is limited to the width (in number of data words) in the SIMD instruction. A change in the vector length of SIMD instructions requires recompiling or even rewriting programs. In contrast, SPMD applications typically spawn a runtime-configurable number of worker threads and can scale on different platforms without recompilation. An SMT core can exploit this parallelism as TLP. Our DITVA proposal further dynamically transforms this TLP into dynamic DLP.

The SIMT execution model

GPUs extract DLP from SPMD workloads by assembling vector instructions across fine-grained threads. GPUs are programmed with SPMD applications, written in low-level languages like CUDA or OpenCL, or compiled from higher-level languages like OpenACC. The SIMT execution model used on NVIDIA GPUs groups threads statically into warps, currently made of 32 threads. All threads in a warp run in lockstep, executing identical instructions. SIMD units execute these warp instructions, each execution lane being dedicated to one thread of the warp. To allow threads to take different control flow paths through program branches, a combination of hardware and software enables differentiated execution based on per-thread predication. On NVIDIA GPU architectures, a stack-based hardware mechanism keeps track of the paths that have diverged from the currently executing path. It follows explicit divergence and reconvergence instructions inserted by the compiler [START_REF] Nickolls | The GPU computing era[END_REF].

Like DITVA, SIMT architectures can vectorize the execution of multi-threaded applications at warp granularity, but they require a specific instruction set to convey branch divergence and reconvergence information to the hardware. GPU compilers have to emit explicit instructions to mark reconvergence points in the binary program. These mechanisms are designed to handle userlevel code with a limited range of control-flow constructs. The stack-based divergence tracking mechanism does not support exceptions or interruptions, which prevents its use with a generalpurpose system software stack. Various works extend the SIMT model to support more generic code [START_REF] Diamos | SIMD re-convergence at thread frontiers[END_REF][START_REF] Menon | iGPU: exception support and speculative execution on GPUs[END_REF] or more flexible execution [START_REF] Wilson | Dynamic warp formation: Efficient MIMD control flow on SIMD graphics hardware[END_REF][START_REF] Brunie | Simultaneous branch and warp interweaving for sustained GPU performance[END_REF][START_REF] Lashgar | HARP: Harnessing inactive threads in many-core processors[END_REF]. However, they all target applications specifically written for GPUs, rather than general-purpose parallel applications.

SMT

SMT improves the throughput of a superscalar core by enabling independent threads to share CPU resources dynamically. Resource sharing policies have [START_REF] Tullsen | Simultaneous multithreading: Maximizing on-chip parallelism[END_REF][START_REF] Tullsen | Exploiting choice: Instruction fetch and issue on an implementable simultaneous multithreading processor[END_REF][START_REF] Cazorla | Dynamically controlled resource allocation in SMT processors[END_REF][START_REF] Luo | Boosting SMT performance by speculation control[END_REF][START_REF] El | Front-end policies for improved issue efficiency in SMT processors[END_REF][START_REF] Eyerman | A memory-level parallelism aware fetch policy for SMT processors[END_REF] huge impact on execution throughput. Many studies have focused on optimizing the instruction fetch policy and leaving the instruction core unchanged while other studies have pointed out the ability to benefit from memory level parallelism through resource sharing policies. Fairness among threads has been recognized as an important property that should be also tackled by resource sharing policies [START_REF] Luo | Balancing thoughput and fairness in SMT processors[END_REF]. However, these resource sharing heuristics essentially address multi-program workloads.

DITVA targets SPMD applications, where threads run the same code. Unlike GPUs that rely on hard explicit reconvergence points, DITVA relies on resource sharing policies to restore lockstep execution of threads. In the past studies, a few policies favoring lockstep or near lockstep execution of threads execution have been proposed. A simple heuristic, which we will refer as Min-PC, prioritizes the threads based on the minimum value of their Program Counter (PC) [START_REF] Michael J Quinn | Compiling c* programs for a hypercube multicomputer[END_REF][START_REF] Lee | Exploring the tradeoffs between programmability and efficiency in data-parallel accelerators[END_REF]. It is based on the idea that compilers typically lay out basic blocks in memory in a way that preserves dominance relations: reconvergence points have a higher address than the matching divergence points. This heuristics will fail if the compiler heavily reorders the basic blocks. Similar heuristics has also been used in the GPU context to synchronize multiple warps together without relying on reconvergence points [START_REF] Wilson | Dynamic warp formation: Efficient MIMD control flow on SIMD graphics hardware[END_REF][START_REF] Veynu Narasiman | Improving GPU performance via large warps and two-level warp scheduling[END_REF]. MinSP-PC was proposed [START_REF] Sylvain | Stack-less simt reconvergence at low cost[END_REF] to improve MinPC heuristic by first prioritizing threads based on the minimum relative value of the stack pointer. The underlying assumption here is that the size of the stack increases with each function call, resulting in a lower value of stack pointer. Therefore, the threads inside inner-most function calls are given priority.

Minimal Multi-threading [START_REF] Long | Minimal multi-threading: Finding and removing redundant instructions in multi-threaded processors[END_REF] or MMT is the closest proposition to DITVA. MMT tries to favor thread synchronization in the front-end (instruction fetch and decode) of an SMT core. It further tries to eliminate redundant computation on the threads. However, MMT assumes a conventional out-of-order execution superscalar core and does not attempt to synchronize instructions within the backend. DITVA keeps instructions synchronized throughout the pipeline, allowing a resource-efficient in-order SIMD backend. In the same spirit, Execution Drafting [START_REF] Mckeown | Execution drafting: Energy efficiency through computation deduplication[END_REF] seeks to synchronize threads running the same code and shares the instruction control logic to improve energy efficiency. It targets both multi-thread and multi-process applications by allowing lockstep execution at arbitrary addresses.

Both MMT and Execution Drafting attempt to run all threads together in lockstep as much as possible. However, we find that full lockstep execution is not always desirable as it defeats Inria the latency tolerance purpose of SMT. The threads running in lockstep will all stall at the same time upon encountering a pipeline hazard like a cache miss, causing inefficient resource utilization. To address this issue, DITVA groups threads into SIMT-style warps, which are scheduled independently and provide latency hiding capabilities. [START_REF] Sylvain | Stack-less simt reconvergence at low cost[END_REF] The Dynamic Inter-Thread Vectorization Architecture

In this section, we present Dynamic Inter-Thread Vectorization Architecture (DITVA). The threads are executed on m execution lanes, 3 on Figure 2. Each lane replicates the register file and the functional units. The thread contexts are statically partitioned into n groups of m threads, one thread per lane. We will refer to such a group as a warp following NVIDIA GPU terminology, e.g. T1,0, T1,1 and T1,2 form Warp 1. A given thread is assigned to a fixed lane, e.g. T0,1 executes on Lane 1. We use the notation nW ×mT to represent a DITVA configuration with n Warps and m Threads per warp. A nW × 1T DITVA is equivalent to a n-thread SMT, while 1W × mT DITVA performs dynamic vectorization across all threads.

On DITVA, whenever the threads of a warp in an SPMD application are synchronized, i.e., have the same PC, the DITVA pipeline executes the instructions from all the threads as a single dynamic vector instruction. The instruction is fetched only once for all the threads of the warp, and a single copy of the instruction flows through the pipeline. That is, decode, dependency check, issue and validation are executed only once, but execution, including operand read, operation execution and register result write-back is performed in parallel on the m lanes.

DITVA supports dynamic vectorization of non-SIMD instructions as well as statically vectorized SIMD instructions such as SSE and AVX.

In the remainder of the section, we first describe the modifications required in the pipeline of an in-order SMT processor to implement DITVA and particularly in the front-end engine to group instructions to be executed in lockstep mode. Then we address the specific issue of data memory accesses. Finally, as maintaining/acquiring lockstep execution mode is the key enabler to DITVA efficiency, we describe the fetch policies that could favor such acquisition after a control flow divergence.

Notations We will refer to the group of threads from the same process running in lockstep with the same PC as a DV-thread. Likewise, a vector of instruction instances from different threads with the same PC is referred to as a DV-instruction. A DV-instruction consisting of scalar instructions are referred to as DV-scalar and those with SIMD instructions such as AVX and SSE are referred to as DV-SIMD. We will refer to the group of registers Ri from the set of hardware contexts in a DITVA warp as the DV-register DRi, and the group of a replicated functional unit as a DV functional unit.

Pipeline architecture

We describe the stages of the DITVA pipeline, as illustrated in Figure 3.

Front end

On an SMT processor, on each cycle, a thread is selected based on an instruction fetch steering policy [START_REF] Tullsen | Simultaneous multithreading: Maximizing on-chip parallelism[END_REF][START_REF] Tullsen | Exploiting choice: Instruction fetch and issue on an implementable simultaneous multithreading processor[END_REF][START_REF] Cazorla | Dynamically controlled resource allocation in SMT processors[END_REF][START_REF] Luo | Boosting SMT performance by speculation control[END_REF][START_REF] El | Front-end policies for improved issue efficiency in SMT processors[END_REF][START_REF] Eyerman | A memory-level parallelism aware fetch policy for SMT processors[END_REF]. Then a block of instructions from the selected thread is fetched from the I-cache and then forwarded to the whole pipeline. This allows all the threads to share the instruction cache without encountering any inter-thread I-cache bank conflict. At the same time, the speculative PC of the next block of instructions is predicted using the branch history of the selected thread. After the decode stage, instructions are pushed into an instruction queue associated with the selected thread.

On DITVA, threads are encapsulated in a two-level structure. Each warp features from 1 to m active DV-threads. In turn, each DV-thread tracks the state of 1 to m scalar threads (Figure 4a). Within the front-end, the basic unit of scheduling is the DV-thread. The state of Inria one DV-thread consists of one process identifier, one PC and an m-bit mask that tracks which threads of the warp belong to the DV-thread. Bit i of the mask is set when thread i within the warp is part of the DV-thread. Also, each DV-thread has data used by the fetch steering policy, such as the call-return nesting level (Section 4.3).

Branch prediction and re-convergence detection Both the PC and mask of each DVthread are speculative. An instruction address generator initially produces a PC prediction for one DV-thread. After the instruction address generation, the PC and process identifier of the predicted DV-thread T are compared with the ones of the other DV-threads. A match indicates that the two DV-threads have reached a point of re-convergence and may be merged. When merging happens, the mask of T is updated to the logical OR of its former mask and the mask of the other DV-thread. The second DV-thread is aborted. Figures 4a and4b illustrates the re-convergence for Warp 0 where threads DV-T2 and DV-T0 re-converge at PC 142. When no re-convergence is detected, the mask of the DV-thread is unaffected. All the threads of the DVthread share the same instruction address generation, by speculating that they will all follow the same branch direction. Accordingly, thread divergence within a DV-thread will be handled as a branch misprediction (Section 4.1.4).

Fetch and decode

Reflecting the two-level organization in warps and DV-threads, instruction fetch obeys two fetch steering policies. First, a warp is selected following a similar policy as in the SMT case. Then, an intra-warp instruction fetch steering policy (that will be described in Section 4.3) selects one DV-thread within the selected warp. From the selected DV-thread PC, a block of instructions is fetched.

Instructions are decoded and turned into DV-instructions, by assigning them an m-bit speculative mask. The DV-instruction then progresses in the pipeline as a single unit. The DVinstruction mask indicates which threads are expected to execute the instruction. Initially, the mask is set to the DV-thread mask. However, as the DV-instruction flows through the pipeline, its mask can be narrowed by having some bits set to zero whenever an older branch is mispredicted or an exception is encountered for one of its active threads.

After the decode stage, the DV-instructions are pushed in a DV-instruction queue, DVIQ. In a conventional SMT, instruction queues are typically associated with individual threads. DITVA follows a similar model, but applies it at the DV-thread granularity: each DVIQ tail is associated with one DV-thread. Unlike in SMT, instructions that are further ahead in the DVIQ may not necessarily belong to the DV-thread currently associated with the DVIQ, due to potential DVthread divergence and reconvergence. The threads that own a given instruction are explicitly identified by the DV-instruction mask, rather than implicitly by their home queue.

In-order issue enforcement and dependency check

On a 4-issue superscalar SMT processor, up to 4 instructions are picked from the head of the instruction queues on each cycle. In each queue, the instructions are picked in-order. In a conventional in-order superscalar microprocessor, the issue queue ensures that the instructions are issued in-order. In DITVA, instructions from a given thread T may exist in one or more DVIQs. To ensure in-order issue in DITVA, we maintain a sequence number for each thread. Sequence numbers track the progress of each thread. On each instruction fetch, the sequence numbers of the affected threads are incremented. Each DV-instruction is assigned an m-wide vector of sequence numbers upon fetch, that correspond to the progress of each thread fetching the instruction. The instruction issue logic checks that sequence numbers are consecutive for successively issued instructions of the same warp. As DVIQs maintain the order, there will always be one such instruction at the head of one queue for each warp.

The length of sequence numbers should be dimensioned in such a way that there is no possible ambiguity in comparing two sequence numbers. The ambiguity is avoided by using more sequence numbers than the maximum number of instructions belonging to a given thread in all DVIQs, which are bounded by the total number of DVIQ entries assigned to a warp. For instance, if the size of DVIQs is 16 and m = 4, 6-bit sequence numbers are sufficient, and each DV-instruction receives a 24-bit sequence vector.

A DV-instruction cannot be launched before all its operands are available. A scoreboard tracks instruction dependencies. In an SMT having n threads with r architectural registers each, the scoreboard consists of a nr data dependency table with 8 ports indexed by the source register IDs of the 4 pre-issued 2-input instructions. In DITVA, unlike in SMT, an operand may be produced by several DV-instructions from different DV-threads, if the consumer instruction lies after a reconvergence point. Therefore, the DITVA scoreboard mechanism must take into account the masks of all the previous in-flight DV-instructions of the warp to ensure operand availability, including instructions from other DVIQs. A straightforward scoreboard implementation uses a nr × m table of masks with 8m ports. However, sequence numbers ensure that each thread issues at most 4 instructions per cycle. The scoreboard can be partitioned between threads as m tables of nr entries with 8 ports.

Execution: register file and functional units

On an in-order SMT processor, the register file features n instances of each architectural register, one per thread. Each register is accessed individually. The functional units are not strictly associated with a particular group of registers and an instruction can read its operands or write its result to a single register file.

In contrast, DITVA implements a split register file; each of the m sub-files implements a register context for one thread of each warp. DITVA also replicates the scalar functional units m times and uses the existing SIMD units of a superscalar processor for the execution of statically vectorized SIMD instructions. However, DITVA factorizes the control.

Figure 5a shows the execution of DV-scalar instruction in a 4×4 DITVA. A DV-scalar reads DV-registers (SRF), i.e. reads from the same registers in the m register files for all the threads of a warp, executes on a DV-unit, i.e. on m similar functional units and writes the m results to the same register in the m register files. All these actions are conditioned by the mask of the DV-instruction. Thus, for DV-scalar instructions, the DITVA back-end is essentially equivalent to an SIMD processor with per-lane predication.

Instruction sets with SIMD extensions often support operations with different vector lengths on the same registers. Taking the x86_64 instruction set as an example, AVX instructions operate on 256-wide registers, while packed SSE instructions support 128-bit operations on the lower halves of AVX architectural registers. Scalar floating-point operations are performed on the low-order 64 or 32 bits of SSE/AVX registers. Whenever possible, DITVA keeps explicit vector instructions as contiguous vectors when executing them on SIMD units. That is, data-level parallelism comes in priority from explicit vector instructions, then from dynamic vectorization across threads. This allows to maintain the contiguous memory access patterns when reading and writing vectors in memory. However, in order to efficiently support partial access to vector registers, the vector register file of DITVA is banked using a hash function. Rather than making each execution lane responsible for a fixed slice of vectors, slices are distributed across lanes in a different order for each thread. For a given thread i, the lane j is responsible for the slide i ⊕ j, ⊕ being the exclusive or operator. All registers within a given lane of a given thread are allocated Inria on the same bank, so the bank index does not depend on the register index.

This banking enables both contiguous execution of full 256-bit AVX instructions, and partial dynamic vectorization of 128-bit vector and 64-bit scalar SSE instructions to fill the 256-bit datapath. Figure 5b shows the execution of a scalar floating-point DV-instruction operating on the low-order 64-bit of AVX registers. The DV-instruction can be issued to all lanes in parallel, each lane reading a different instance of the vector register low-order bits. For a 128-bit SSE DV-instruction, lanes 0,2 or 1,3 can be executed in the same cycle. Figure 5c shows the pipelined execution of a SSE DV-instruction with mask 1011 in a 4×4 DITVA. In figure 5c, T0 and T2 are issued in the first cycle and T1 is issued in the subsequent cycle. Finally, full-width AVX instructions within a DV-instructions are issued in successive cycles to a pipelined functional unit. Figure 5d shows the execution of a AVX DV-instruction with mask 1101 in a 4 × 4 DITVA. Division operations are not pipelined, and their execution are completely serialized.

As the DITVA processor is p-issue superscalar, on each cycle up to p independent DVinstructions are picked from the heads of the DVIQs.

Handling misprediction, exception or divergence

Branch mispredictions or exceptions require repairing the pipeline. On an in-order SMT architecture, the pipeline can be repaired through simply flushing the subsequent thread instructions from the pipeline and resetting the speculative PC to the effective PC.

In DITVA, mispredictions or exceptions may be either partial or total, depending on whether or not all the threads within the DV-thread encounter the event. A partial branch misprediction corresponds to DV-thread divergence when some threads of the DV-thread follow a different direction than the correctly-predicted threads. Handling an exception would be similar to handling a branch misprediction.

On DITVA, on a mispredicted branch, partial or total, for every mispredicted thread T, the following actions must be done.

1. Reset the speculative thread PC of T to its effective PC.

Remove the Instructions from T from the pipeline.

As the DV-instructions encapsulates the thread instructions, the point 1 can be managed as follows. First, mispredicted threads are grouped into sets of same-PC threads, to form a new DV-thread on each mispredicted path. In the case of a two-sided conditional branch, there is only one set containing all mispredicted threads. Then, the initial DV-thread is split between the correctly-predicted path and each mispredicted path. In this scenario, the bits corresponding to mispredicted threads are cleared in the mask of the initial DV-thread and spawns a new DVthread for each mispredicted path. The sequence numbers of the threads in the new DV-thread are reset to follow the sequence numbers of the branch instruction in each thread.

To implement point 2, the bits corresponding to the mispredicted threads are cleared in all the masks of the DV-instructions in progress in the pipeline and in the DVIQ. This corresponds to disabling all the instructions fetched from the wrong path for each thread T. Figure 4b shows the state of the pipeline when the instruction PC-11d of thread T5 illustrated in figure 4a triggers a branch misprediction. In the given example, a new DV-thread is spawned for thread T5, which starts fetching from the other branch after misprediction.

In addition, some bookkeeping is needed. In the case of a full misprediction, the masks of some DV-instructions become null, i.e. no valid thread remains. These DV-instructions have to be flushed out from the pipeline to avoid consuming bandwidth at execution time. This bookkeeping is kept simple as null DV-instructions are at the head of the DVIQ. Likewise, a DV-thread with an empty mask is aborted.

As DITVA provisions m DV-thread slots per warp, and the masks of DV-threads do not overlap, resources are always available to spawn the new DV-threads upon a misprediction. The only case when all DV-threads slots are occupied is when each DV-thread has only one thread. In that case, a misprediction can only be a full misprediction, and the new DV-thread can be spawned in the slot left by the former one.

Full branch mispredictions in DITVA have the same performance impact as a misprediction in SMT, i.e. the overall pipeline must be flushed for the considered DV-warp. On the other hand, partial misprediction has no significant performance impact as both branch paths are eventually taken.

Data memory accesses

A DV-load (resp. DV-store) of a full 256-bit AVX DV-SIMD instruction is pipelined. Each data access request corresponding to the participant thread is serviced in the successive cycles. For a 128-bit SSE DV-SIMD instruction, data access operation from lane 0,2 or 1,3 are serviced in the same cycle. Any other combination of two or more threads are pipelined. For example, a DV-load with threads 0,1 or 0,1,2 would be serviced in 2 cycles. A data access operation in a DV-scalar instruction may have to access up to m data words in the cache. These m words may belong to m distinct cache lines and/or to m distinct virtual pages. Servicing these m data accesses on the same cycle would require a fully multiported data cache and a fully multiported data TLB.

The hardware cost of a multiported cache is very high. In particular when the data are truly shared, and handling multiple writes requires implementing effective multiple ports (and not just simple replication of the data cache). Therefore, the proposed implementation of DITVA relies on a banked data cache. Banking is performed at cache line granularity. In case of conflicts, the execution of a DV-load or a DV-store stays atomic and spans over several cycles, thus stalling the pipeline for all its participating threads. The load data path must be able to support the special cases of several threads accessing the same element, for both regular and atomic memory operations.

It is possible to use a fully hashed set index to reduce bank conflicts, assuming a virtually indexed L1 data cache. Our experiments in section 5 illustrate the reduction in the number of data access conflicts due to the alignment of the bottom of thread stacks on page boundaries.

Maintaining equal contents for the m copies of the TLB is not as important as it is for the data cache: there are no write operations on the TLB. Hence, the data TLB could be implemented just as m copies of a single-ported data TLB. However, the threads do not systematically use the same data pages. That is, Thread I only references the pages directly accessed by it in the data TLB associated with itself. Our simulations in Section 5 show that this optimization significantly decrease the total number of TLB misses or allows to use smaller TLBs.

DITVA executes DV-instructions in-order. Hence, a cache miss on one of the active threads in a DV-load stalls the instruction issue of all the threads in the DV instruction.

Maintaining lockstep execution

DITVA has the potential to provide high execution bandwidth on SPMD applications when the threads execute very similar control flows on different data sets. Unfortunately, threads may lose synchronization as soon as there is a control flow divergence among the threads. Apart the synchronization points inserted by the application developer or the compiler, the instruction fetch policy and the execution priority policy are the two possible vehicles to restore lockstep execution.

Inria

One of the most simple yet fairly efficient fetch policies to reinitiate lockstep execution is MinSP-PC [START_REF] Sylvain | Stack-less simt reconvergence at low cost[END_REF]. The highest priority is given to the thread with the deepest call stack, based on the relative stack pointer address or call/return count. On a tie, the thread that has the minimum PC is selected. Assuming a downward growing stack, MinSP gives priority for the deepest function call nesting level. When there is a tie the priority is based on the minimum value of PC which gives a more fine grained synchronization. However, while experience shows that MinSP-PC tends to synchronize SPMD threads in many cases, there is no guarantee that each thread will make continuous forward progress. MinSP-PC could even lead to deadlocks, e.g. in the event of an active waiting loop. Besides, when going through non-SPMD code sections involving independent threads, applying the MinSP-PC policy would essentially result in executing a single thread, while stalling all other threads.

Therefore, for this study on DITVA, we use a hybrid Round-Robin/MinSP-PC instruction fetch policy. The MinSP-PC policy helps restore lockstep execution and Round-Robin guarantees forward progress for each thread. To guarantee that any thread T will get the instruction fetch priority periodically1 , the RR/MinSP-PC policy acts as follows. Among all the DV-threads with free DVIQ slots, if any DV-thread has not got the instruction fetch priority for (m+1)×n cycles, then it gets the priority. Otherwise, the MinSP-PC DV-thread is scheduled.

This hybrid fetch policy is biased toward the DV-thread with minimum stack pointer or minimum PC to favor thread synchronization, but still guarantees that each thread will make progress. In particular, when all threads within a warp are divergent, the MinSP-PC thread will be scheduled twice every m + 1 scheduling cycles for the warp, while each other thread will be scheduled once every m + 1 cycles.

Since warps are static, convergent execution does not depend on the prioritization heuristics of the warps. The warp selection is done with round robin priority to ensure fairness for each of the independent thread groups.

Evaluation

We simulate DITVA to evaluate its performance and design tradeoffs.

Experimental Framework

We model DITVA using an in-house trace-driven x86_64 simulator. A Pin tool [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF] records one execution trace per thread of one SPMD application. The trace-driven DITVA simulator consumes the traces of all threads concurrently, scheduling their instructions in the order dictated by the fetch steering and resource arbitration policies.

Thread synchronization primitives such as locks need a special handling in this multi-thread trace-driven approach since they affect thread scheduling. We record all calls to synchronization primitives and enforce their behavior in the simulator to guarantee that the order in which traces are replayed results in a valid scheduling. In other words, the simulation of synchronization instructions is execution-driven, while it is trace-driven for all other instructions.

Just like SMT, DITVA can be used as a basic block in a multi-core processor. However, to prevent multi-core scalability issues from affecting the analysis, we focus on the micro-architecture comparison of a single core in this study. To account for memory bandwidth contention effects in a multi-core environment, we simulate a throughput-limited memory with 2 GB/s of DRAM bandwidth per core. This corresponds to a compute/bandwidth ratio of 32 Flops per byte in We evaluate DITVA on SPMD benchmarks from the PARSEC [START_REF] Bienia | The parsec benchmark suite: Characterization and architectural implications[END_REF] and SPLASH 2 [START_REF]Splash-2[END_REF] suites compiled for corei7 -avx architecture. We simulate the following benchmarks: Barnes, Blackscholes, Fluidanimate, FFT, Fmm, Swaptions, Radix, Volrend, Ocean CP and Ocean NCP. Since accurate simulation of the relative progress of threads is fundamental for our study, we simulate entire benchmarks rather than rely on sampling techniques. We obtained the results in this section with the simsmall input dataset.

Figure 6 shows the performance scaling of single-thread and SMT configurations with 4, 8 and 16 threads. Application exhibit diverse scaling behavior with thread count. FFT, Ocean and Radix tend to be bound by memory bandwidth, and their performance plateaus or decreases after 8 threads. Volrend and Fluidanimate also have a notable parallelization overhead due to thread state management and synchronization. In the rest of the evaluation, we will consider the 4-thread SMT configuration (4W × 1T ) with AVX as our baseline. We will consider 4W × 2T DITVA, i.e., 4-way SMT with two dynamic vector lanes and 4W × 4T DITVA, i.e., 4-way SMT with 4 lanes.

Bank conflict reduction

Bank interleaving using the low order bits on the L1 data cache leads to a noticeable number of bank conflicts, as illustrated in Figure 7. We find that many conflicts are caused by concurrent accesses to the stack. When the base addresses of the thread call stacks are aligned on page boundaries, concurrent accesses at the same offset in different stacks result in bank conflicts. This observation matches the findings of prior studies [START_REF] Meng | Avoiding cache thrashing due to private data placement in last-level cache for manycore scaling[END_REF][START_REF] Milanez | Thread scheduling and memory coalescing for dynamic vectorization of SPMD workloads[END_REF].

To reduce such bank conflicts for DV-loads and DV-stores, we use a hashed set index as suggested in Section 4.2. For a 16-bank cache interleaved at 32-bit word granularity, we use lower bits from 12 to 15 and higher bits from 24 to 27 and hash them for banking. Figure 7 illustrates that such a hashing mechanism is effective in reducing bank conflicts on applications where threads make independent sequential memory accesses, such as Blackscholes and FFT. In Inria the remainder of the evaluation section, this hashed set index is used. Dynamic vectorization reduces the number of DV-instructions over original instructions. Figure 9 shows the ratio of the DV-instruction count over the individual instruction count for 4W × 2T DITVA and 4W × 4T DITVA. In average on our benchmark set, this ratio is 74% for 4W × 2T DITVA and 60% for 4W × 4T DITVA. DV-instruction count is low for applications for Radix and FFT, which has nearly perfect dynamic vectorization. However, the DV-instruction count reduction in Volrend, Fluidanimate and Ocean is compensated by the parallelization overhead caused by the thread count increase.

Vectorization efficiency

Throughput

Figure 10 shows the speed-up achieved for 4W × 2T DITVA and 4W × 4T DITVA over 4-thread SMT with AVX instructions. For reference, we illustrate the performance of 16-thread and 8thread SMT (16W × 1T and 8W × 1T respectively). On average, 4W × 2T DITVA achieves 31% higher performance than 4-thread SMT and 4W × 4T DITVA achieves 44% performance improvement. The 4W × 4T DITVA also achieves 20% speedup over 16-thread SMT. The application speedup is due to replicated ALU and efficient utilization of AVX units for the execution of SSE and scalar floating-point instructions.

Due to memory hierarchy related factors, the actual speed-up is not proportional to DVinstruction occupancy. For instance, although Radix has high dynamic vectorization potential, its performance is rather disappointing with four lanes performing worse than two lanes. Indeed, with four lanes and so 16 threads Radix experiences many cache misses that exhausts the memory bandwidth. With two lanes and so only 8 threads, the demand on memory bandwidth is much smaller and some speed-up is encountered. For applications with low DLP, like Fluidanimate, the performance of DITVA is on par with 16-thread SMT. The relative speed up of Fluidanimate, Ocean CP, Ocean NCP and Volrend is impacted by the increase in the number of instructions with the increase in the number of threads.

Impact of split data TLB

Each execution lane of DITVA must feature a data TLB or have an access port to the data TLB, Not only the TLB must be duplicated, but one should also increase its number of entries in order to limit the TLB miss rate, since the number of threads executed on DITVA is larger than the one executed on the 4-thread SMT.

However, as pointed out in Section 4.2, there is no need to maintain equal contents for the TLBs of the distinct lanes. Assuming a 4KB page size, Figure 11 illustrates the TLB miss rates for different configurations: 4-lanes DITVA, i.e., a total of 16 threads, with 128-entry unified TLB, 256-entry unified TLB and 64-entry split TLB, and a 64-entry TLB for the SMT configuration.

On our set of benchmarks, the miss rate of the 64-entry split TLB for four lanes DITVA is in the same range as the one of the 64-entry for SMT. If the TLB is unified, 256-entry is needed to reach the same level of performance. Thus, using split TLBs appears as a sensible option to avoid the implementation complexity of a unified TLB.

Impact of memory bandwidth on memory intensive applications

In the multi-core era, memory bandwidth is a bottleneck for the overall core performance. Our simulations assume 2 GB/s DRAM bandwidth per core. To analyze the impact of DRAM bandwidth on memory intensive applications running on DITVA, we simulate configurations with 16 GB/s DRAM bandwidth which is a feasible alternative in the modern multi-core microprocessors. The performance scaling of 16 GB/s relative to 4-thread SMT with 2 GB/s DRAM bandwidth is illustrated in Figure 12.

For many benchmarks, 2 GB/s bandwidth is sufficient. However, as discussed in section 5.1, the performance of Ocean, Radix and FFT is bound by memory throughput. DITVA enables these applications to benefit from the extra memory bandwidth, widening the gap with the baseline SMT configuration.

Hardware Overhead, Power and Energy

DITVA induces extra hardware complexity and area as well as extra power supply demand over an in-order SMT core. On the other hand, DITVA achieves higher performance on SPMD code. This can lead to reduced total energy consumption on such code.

We analyze qualitatively and quantitatively the sources of hardware complexity, power demand and energy consumption throughout the DITVA pipeline compared with the ones of the corresponding in-order SMT core.

Qualitative evaluation

Pipeline Front End The modifications in the pipeline front-end induce essentially extra logic, e.g. comparators and logic to detect DV-thread reconvergence, the logic to select the DV-thread within the warp, and the DVIQ mask unsetting logic for managing branch mispredictions and exceptions. The extra complexity and power consumption should remain relatively limited. The most power hungry logic piece introduced by the DITVA architecture is the scoreboard that must track the dependencies among registers of up to m DV-threads per warp. However, this scoreboard is also banked since there are no inter-thread register dependencies.

On the other hand, DITVA significantly cuts down dynamic energy consumption in the frontend. Our experiments show a reduction of 40% of instruction fetches for 4W × 4T DITVA.

The memory unit

The DITVA memory unit requires extra hardware. First, bank conflict handling logic is needed, as we consider an interleaved cache. Then, replicated data TLBs add an overhead in area and static energy. Moreover as DITVA executes more threads in parallel than an SMT core, the overall capacity of the TLB must be increased to support these threads. However, as TLB contents do not have to be maintained equal, we have shown that lane TLBs with the same number of entries as a conventional 4-way SMT core would be performance effective. Therefore, on DITVA, the TLB silicon area as well as its static energy consumption is proportional to the number of lanes.

Register file On the register file, an in-order n-thread SMT core features n × NbISA scalar registers of width B bits while a nW × mT DITVA features n × NbISA DV-registers of width Inria m × B bits. Estimations using CACTI [START_REF] Thoziyoor | Cacti 5.1[END_REF] and McPAT indicate that the access time and the dynamic energy per accessed word are in the same range for DITVA and the SMT. The register file silicon area is nearly proportional to m, the number of lanes, and so is its static leakage.

DV-units The replication of the two scalar functional units to form DV-units introduces the most significant hardware area overhead. The DV-units have a higher leakage and require higher instantaneous power supply than the functional units of the in-order execution SMT core. However, DITVA also leverages the existing AVX SIMD units by reusing them as DV-units. Additionally, since DV-units are activated through the DV-instruction mask, the number of dynamic activations of each functional type is roughly the same for DITVA and the in-order SMT core on a given workload, and so does the dynamic energy.

Pipeline Front End The modifications in the pipeline front-end induce essentially extra logic, e.g. comparators and logic to detect DV-thread reconvergence, the logic to select the DV-thread within the warp, and the DVIQ mask unsetting logic for managing branch mispredictions and exceptions. The extra complexity and power consumption should remain relatively limited. The most power hungry logic piece introduced by the DITVA architecture is the scoreboard that must track the dependencies among registers of up to m DV-threads per warp. However, this scoreboard is also banked since there are no inter-thread register dependencies.

On the other hand, DITVA eliminates significant dynamic energy consumption in the frontend. Our experiments show a reduction of 40% of instruction fetches for 4W × 4T DITVA.

Non-SPMD workloads DITVA only benefits shared memory SPMD applications that have intrinsic DLP. On single-threaded workloads or highly divergent SPMD workloads, DITVA performs on par with the baseline 4-way in-order SMT processor. Workloads that do not benefit from DITVA will mostly suffer from the static power overhead of unused units. Moreover, on single-threaded workloads or on multiprogrammed workloads, a smart runtime system could be used to power down the extra execution lanes thus bringing the energy consumption close to the one of the baseline SMT processor.

Non-SPMD multi-threaded workloads may suffer scheduling unbalance (unfairness) due to the RR/MinSP-PC fetch policy. However, this unbalance is limited by the hybrid fetch policy design. When all threads run independently, a single thread will get a priority boost and progress twice as fast as each the other threads. e.g. with 4 threads, the MinSP-PC thread gets 2/5th of the fetch bandwidth, each other thread gets 1/5th.

Quantitative evaluation

We modeled a baseline SMT processor and DITVA within McPAT [START_REF] Li | Mcpat: an integrated power, area, and timing modeling framework for multicore and manycore architectures[END_REF]. It assumes a 2 GHz clock in 45nm technology with power gating. We modeled two alternative designs. The first one is the configuration depicted on Table 1, except the cache that was modeled as 64 KB 8-way as we could not model the banked 32 KB 16-way configuration in McPAT. The dynamic energy consumption modeling is illustrated on Figure 13 while modeled silicon area and static energy are reported in Table 2. As in Section 5, we assume that DITVA is built on top of an SMT processor with 256-bit wide AVX SIMD execution units and that these SIMD execution units are reused in DITVA.

Note that McPAT models execution units as independent ALUs and FPUs, rather than as SIMD blocks as implemented on current architectures. Also, estimations may tend to underestimate front-end energy [START_REF] Sam Likun Xi | Quantifying sources of error in mcpat and potential impacts on architectural studies[END_REF]. Thus, the front-end energy savings are conservative, while the overhead of the back-end is a worst-case estimate. Despite these conservative assumptions, Figure 13 and Table 2 show that DITVA appears as an energy-effective solution for SPMD applications with respectively 20% and 22% average energy reduction for 4W × 2T and 4W × 4T DITVA. The energy reduction is the result of both a decrease in run-time (Figure 10) and a reduction in the number of fetched instructions, mitigated by an increase in static power from the wider execution units.

Conclusion

In this paper, we have proposed the DITVA architecture that aims at partially filling the gap between massively threaded machines, e.g. SIMT GPUs, and SMT general-purpose CPUs. Compared with an in-order SMT core architecture, DITVA achieves high throughput on the parallel sections of the SPMD applications by extracting dynamic data-level parallelism at runtime. DITVA provides a design tradeoff between an in-order SMT core and an SIMT GPU core. It uses dynamic vector execution to allow lockstep parallel execution as in SIMT GPUs, but retaining binary compatibility with existing general-purpose CPUs. Applications require no source modification nor re-compilation.

On DITVA, threads are statically grouped into fixed-size warps. SPMD threads from a warp are dynamically vectorized at instruction fetch time. The instructions from the different threads are grouped together whenever their PC are equal. Then the group of instructions (the DVinstruction) progresses in the pipeline in lockstep mode. This allows to mutualize the instruction front-end as well the overall instruction control. The instructions from the different threads in a DV-instruction are executed on replicated execution lanes. DITVA maintains a competitive single-thread and divergent multi-thread performance by using branch prediction and speculative predicated execution. By relying on a simple thread scheduling policy favoring reconvergence and by handling branch divergence at the execute stage as a partial branch misprediction, most of the complexity associated with tracking and predicting thread divergence and reconvergence can be avoided. To support concurrent memory accesses, DITVA implements a bank-interleaved cache with a fully hashed set index to mitigate bank conflicts. DITVA leverages the possibility to use TLBs with different contents for the different threads. It uses a split TLB much smaller than the TLB of an in-order SMT core.

Our simulation shows that 4W × 2T and 4W × 4T lanes DITVA processors are cost-effective design points. For instance, a 4W ×4T DITVA architecture reduces instruction count by 40% and improving performance by 44% over a 4-thread 4-way issue SMT on the SPMD applications from PARSEC. While a DITVA architecture induces some silicon area and static energy overheads over an in-order SMT, by leveraging the preexisting SIMD execution units to execute the DVinstructions, DITVA can be very energy effective to execute SPMD code. Therefore, DITVA appears as a cost-effective design for achieving very high single-core performance on SPMD Inria parallel sections. A DITVA-based multi-core or many-core would achieve very high parallel performance.

As DITVA shares some of its key features with the SIMT execution model, some microarchitecture improvements proposed for SIMT could also apply to DITVA. For instance, more flexibility could be obtained using Dynamic Warp Formation [START_REF] Wilson | Dynamic warp formation: Efficient MIMD control flow on SIMD graphics hardware[END_REF] or Simultaneous Branch Interweaving [START_REF] Brunie | Simultaneous branch and warp interweaving for sustained GPU performance[END_REF], while Dynamic Warp Subdivision [START_REF] Meng | Dynamic warp subdivision for integrated branch and memory divergence tolerance[END_REF] could improve latency tolerance by allowing threads to diverge on partial cache misses.

Figure 1 :

 1 Figure 1: Control flow graph of blackscholes benchmark

Figure 2 :

 2 Figure 2: A logical view of the DITVA architecture

Figure 3 :

 3 Figure 3: Overview of the DITVA pipeline

Figure 8

 8 Figure 8 illustrates the DV functional unit occupancy with a breakdown of individual instructions count per DV-instruction on DITVA 4W × 4T . The k thread bar represents the normalized frequency of occurrence of DV-instructions with k active threads. This figure represents the DLP that could be extracted from the SPMD program. Radix and FFT have vast amounts of DLP. Hence, most of their instructions are perfectly combined to form DV-instructions. On the other hand, the threads of benchmarks that have low exploitable DLP like Fluidanimate tend to diverge. Only 23% of DV-instructions contain more than one instruction on Fluidanimate.Dynamic vectorization reduces the number of DV-instructions over original instructions. Figure9shows the ratio of the DV-instruction count over the individual instruction count for 4W × 2T DITVA and 4W × 4T DITVA. In average on our benchmark set, this ratio is 74% for 4W × 2T DITVA and 60% for 4W × 4T DITVA. DV-instruction count is low for applications for Radix and FFT, which has nearly perfect dynamic vectorization. However, the DV-instruction count reduction in Volrend, Fluidanimate and Ocean is compensated by the parallelization overhead caused by the thread count increase.

  After reconvergence in Warp 0 and misprediction in Warp 1

Figure 4 :Figure 5 :

 45 Figure 4: Evolution of the DV-thread and DVIQ states upon thread divergence and reconvergence

Figure 6 :Figure 7 :Figure 8 :Figure 9 :Figure 10 :Figure 11 :Figure 12 :Figure 13 :

 678910111213 Figure 6: Speedup with thread count in the baseline SMT configuration, normalized to singlethread performance

Table 1 :

 1 Simulator parameters

		Configuration
	L1 data cache	32 KB, 16 ways LRU, lat 2 cycles
	L2 cache	4MB, 16 ways LRU, lat 15 cycles
	L2 miss latency	215 cycles
	Cache banks	16
	Branch predictor	64-Kbit TAGE [30]
	DVIQs	n × m 16-entry queues
	DV-thread select	MinSP-PC + RR every n(m + 1) cycles
	Fetch and decode	4 instructions per cycle
	Issue width	4 DV-instructions per cycle
	Functional units (SMT)	4 64-bit ALUs, 2 256-bit AVX/FPUs, 1 mul/div, 1 256-
		bit load/store, 1 branch
	Functional units (DITVA) 2 n × 64-bit ALUs, 2 256-bit AVX/FPUs, 1 n × 64-bit
		mul/div, 1 256-bit load/store

the 4W × 4T DITVA configuration, which is representative of current multi-core architectures. We compare two DITVA core configurations against a baseline SMT processor core with AVX units. Table

1

lists the simulation parameters of both micro-architectures. DITVA leverages the 256-bit AVX/FPU unit to execute scalar DV-instructions in addition to the 2 n × 64-bit ALUs, achieving the equivalent of 4n × 64-bit ALUs.

Table 2 :

 2 Area and static power McPAT estimates.

	Component	4T SMT	4W×2T DITVA 4W×4T DITVA
		Area	Static	Area	Static	Area	Static
		(mm 2 )	P.	(mm 2 )	P.	(mm 2 )	P.
			(W)		(W)		(W)
	Front-end	3.46	0.140	3.63	0.149	4.14	0.175
	LSU	1.32	0.050	2.21	0.041	2.33	0.054
	MMU	0.22	0.009	0.32	0.012	0.50	0.018
	Execute	20.98	0.842	21.51	0.868	22.40	0.920
	Core total	35.50	1.815	37.30	1.868	39.09	2.001

RR n°8830

RR/MinSP-PC is not completely fair among independent threads, e.g. multiple program workloads as it may favor some threads. However, fairness on this type of workloads is out of the scope of this paper.RR n°8830