Danny Holten
email: d.h.r.holten@tue.nl

Petra Isenberg
email: petra.isenberg@inria.fr

Jean-Daniel Fekete
email: jean-daniel.fekete@inria.fr

Jarke J Van Wijk

Performance Evaluation of Tapered, Curved, and Animated Directed-Edge Representations in Node-Link Graphs LaQuSo *

 showed that this arrow representation was not optimal. Their user study compared the performance (in terms of reading time and correctness) of various directed-edge representations. A tapered representation -wide at the start and narrow at the end -showed the best performance. This paper presents the results of a follow-up study comparing the performance of the tapered representation with two other representations: one using biased curvature and the other using animation to indicate edge direction. We tested the three representations using a more realistic setting than the original article. We used random small-world graphs generated with the Barabási-Albert model, we used the Fruchterman-Reingold algorithm to lay out the graphs, and we varied graph density and link length to measure their influences. Overall, our study shows that the tapered and animated representations perform significantly better than the biased-curvature representation, with no significant differences between tapered and animated except for medium-length representations where tapered was faster. The article presents detailed results and provides practical recommendations on the use of directed-edge representations.

Introduction

Graph-based data, which is used to represent a collection of elements (vertices) as well as the connections (edges) between these elements, has become ubiquitous these days, not least due to the increasing popularity of social networking sites on the Internet. Apart from social network graphs (or social networks), where vertices represent individuals and edges represent acquaintance, the following lists some additional examples of common graph-based data sources:

• Traffic networks, where vertices and edges are used to represent locations and traffic routes, respectively;

• Computer networks, where vertices and edges are used to represent PCs and network connections, respectively;

• Scientific citation networks, where vertices and edges are used to represent papers and citations between papers, respectively.

Edges often have an associated weight and direction. Edge weight might be used to indicate the strength, importance, or cost of an edge. Edge direction can be used to signify the directionality of what an edge represents, e.g., which paper holds a citation and which paper is being cited in case of a citation network graph.

When visualizing a graph, an often-used and intuitive visual representation is the node-link diagram (node-link graph), in which vertices are generally represented as circular nodes and edges as straight or curved links (lines). Edge weight is commonly depicted by varying the width of a link, while edge direction is generally depicted using an arrow representation, i.e., a line with an arrowhead at Node B in case of a directed edge running from Node A to Node B.

Holten and Van Wijk noted that the use of an arrow representation can lead to visual clutter because of arrowhead overlap, which can significantly hinder effortless and correct observation of edge direction [START_REF] Holten | A User Study on Visualizing Directed Edges in Graphs[END_REF]. Various approaches can be used to overcome this, such as adding user interaction, using a matrix instead of a node-link representation, improving the node-link layout, or improving the directed-edge representation. However, user interaction is not suited for statically depicted, e.g., printed, graphs; matrix representations have been shown to be less intuitive than node-link graphs [START_REF] Ghoniem | A Comparison of the Readability of Graphs Using Node-Link and Matrix-Based Representations[END_REF][START_REF] Keller | Matrices or Node-Link Diagrams: Which Visual Representation is Better for Visualising Connectivity Models?[END_REF]; and node-link-layout improvement is generally tackled by nodeplacement optimization, while the arrowhead-clutter problem actually stems from a sub-optimal edge representation.

For this reason, we contend that focusing on the use of improved directed-edge representations is warranted. This was also done by Holten and Van Wijk [START_REF] Holten | A User Study on Visualizing Directed Edges in Graphs[END_REF], who performed a user study (henceforth called "the initial study") in which participants performed various tasks on a collection of graphs using different directed-edge representations (including the standard arrow) to investigate which of these representations lead to the best accuracy and reading times. They concluded that a tapered representation clearly outperformed the other representations. This representation generalizes the notion of an arrowhead by gradually varying the width of a link along its length, i.e., wide at the start and narrow at the end.

This paper presents a follow-up study that was inspired by the choices, experiments, and future work suggestions that were part of the initial study [START_REF] Holten | A User Study on Visualizing Directed Edges in Graphs[END_REF]. Among other things, the evaluation of animated directed-edge representations is suggested. Furthermore, one of the directed-edge representations that was evaluated uses clockwise curvature to indicate edge direction, which showed poor performance. We therefore chose to evaluate the performance of 1) tapered, the best representation according to the initial study, 2) an animated rep-resentation, and 3) a representation that uses biased clockwise curvature -high curvature at the start, low curvature at the end -as proposed by Fekete et al. [START_REF] Fekete | Overlaying Graph Links on Treemaps[END_REF]. This curvature-based representation is regularly used and might perform better than the non-biased curvature-based representation evaluated in the initial study.

We furthermore evaluated how performance in terms of reading time and correctness is affected by three levels of graph density (sparse, medium density, and dense) as well as three different link-length classes (short, medium length, and long).

Finally, we used a class of graphs that is more representative of real-world graphs such as social networks, i.e., scale-free (small-world) graphs in which the degree distribution follows a power law [START_REF] Watts | Collective Dynamics of Small-World Networks[END_REF][START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF]; the graph model used in the initial study to generate the graphs was a non-scale-free model [START_REF] Ware | Supporting Visual Queries on Medium-Sized Node-Link Diagrams[END_REF][START_REF] Ware | Visualizing Graphs in Three Dimensions[END_REF]. We used the well-known Fruchterman-Reingold algorithm [START_REF] Fruchterman | Graph Drawing by Force-Directed Placement[END_REF] to generate the graph layouts.

To evaluate the actual performance of the directed-edge representations in terms of reading time and correctness, we designed and ran an experiment in which participants performed path-readability trials, i.e., they had to answer whether or not there was a directed connection between a pair of nodes. We provide initial hypotheses regarding the performance of the evaluated directed-edge representations with respect to varying graph densities and link lengths, and subsequently compare these with the outcome of a statistical analysis of participants' reading times and correctness. Based on the results of this analysis, we provide practical recommendations on the use of directed-edge representations in the context of nodelink graphs.

The remainder of the paper is organized as follows. Section 2 describes previous work on directed-edge visualization, the evaluation thereof, and the use of static, animated, and curvature-based representations to show direction. Section 3 gives an overview of graph generation and layout, the evaluated representations, and the selection of node pairs during trials. The experiment design and hypotheses are presented in Section 4, followed by Section 5, which presents the statistical analysis. Practical recommendations on directed-edge usage are provided in Section 6. Finally, Section 7 presents our conclusions and suggestions for future work.

Related Work

The following presents an overview of various directed-edge representations that have been proposed in the past, the majority of which are straight, static representations that have been used in the context of node-link graphs to depict directed connectivity. The use of edge representations that rely on curvature and animation is treated separately in Sections 2.2 and 2.3, respectively.

Straight, Static Directed-Edge Representations

Half-lines are used by Becker et al. [START_REF] Becker | Visualizing Network Data[END_REF] to depict directed edges; a half-line from Node A to B is a straight-line connection in which only the first half of the line is drawn. Although half-lines reduce the amount of display space used to show links, they unfortunately make it hard to determine where links end. Wong et al. [START_REF] Wong | Dynamic Visualization of Graphs with Extended Labels[END_REF] present their GreenArrow technique as a solution to the problem of how to balance the appearance of both a graph and its labels. The text label pertaining to a link (or one of its nodes) is drawn such that the text itself forms a tapered link between two nodes. This removes the need to explicitly visualize the edge using a line-based representation. A color-coded representation is used by Holten [START_REF] Holten | Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data[END_REF] to indicate edge direction. Direction is indicated as running from Node A to Node B by gradually changing the color from green (A) to red (B) along the length of a link, although different colors can be used as well.

The directed-edge representations that were evaluated (and partially designed) in the initial study [START_REF] Holten | A User Study on Visualizing Directed Edges in Graphs[END_REF] are the standard arrow, tapered, curved (non-biased, clockwise direction), greento-red, light-to-dark, and dark-to-light. The following combinations were furthermore evaluated: tapered + curved, tapered + dark-to-light, curved + dark-to-light, and tapered + dark-tolight + curved. Apart from the recommendation of using a tapered representation in general because of its performance, is was also found that combining representations (at least the ones that were evaluated) did not result in significant performance gains. Nielsen et al. [START_REF] Nielsen | ABySS-Explorer: Visualizing Genome Sequence Assemblies[END_REF] note that they were partially inspired by these recommendations. For their ABySS-Explorer they use tapered, leaf-like shapes to visually depict the orientation of contigs, i.e., genome assemblies consisting of long contiguous sequences.

Curvature-Based Directed-Edge Representations

Edge representations based on curvature have been used before in the context of Arc Diagrams by Wattenberg [START_REF] Wattenberg | Arc Diagrams: Visualizing Structure in Strings[END_REF] Instead of only using (counter-)clockwise orientation to indicate direction, Fekete et al. [START_REF] Fekete | Overlaying Graph Links on Treemaps[END_REF] add curvature bias to this. Their curved links are drawn as quadratic Bézier curves that vary the amount of curvature -high at the start and low at the end -to indicate direction (see Figure 2b). This is one of the representations that we evaluated since it is regularly used and we hypothesized that it might be a better alternative than the simple, non-biased clockwise-curvature-based representation evaluated in the initial study.

Animated Directed-Edge Representations

Most animated edge representations indicate edge direction based on the idea of having a dash pattern move in the direction of the link along the length of a link. An example is the effective use of animated dash-pattern textures by Wegenkittl et al. [START_REF] Wegenkittl | A Guided Tour to Wonderland: Visualizing the Slow-Fast Dynamics of an Analytical Dynamical System[END_REF] to show the flow motion of trajectories within analytical dynamical systems.

To address node and link clutter in large and dense nodelink graphs, Ware et al. [START_REF] Ware | Motion to Support Rapid Interactive Queries on Node-Link Diagrams[END_REF] evaluated motion-based highlighting techniques to provide effective access to such graphs. One of the evaluated techniques was an edge representation that uses animated sawtooth dash patterns radiating out from the source (start) node. For the path-readability and nodereachability tasks that participants performed, reading time and error rate were generally significantly lower when using animated-link highlighting than when using no highlighting. Ware et al. therefore argue that motion-based highlighting can be valuable in applications that require users to understand large graphs.

Bartram et al. [START_REF] Bartram | Animating Causal Overlays[END_REF] showed the potential of using animated causal overlays, e.g., animated links, on top of causalitydepicting visualizations such as causal graphs. The idea was inspired by the fact that perceptual psychology showed that causality perception is a low-level visual event derived from certain types of motion.

Blaas et al. [START_REF] Blaas | Smooth Graphs for Visual Exploration of Higher-Order State Transitions[END_REF] present a spline-based way to smoothly visualize higher-order state transitions for the exploration of state sequences in large time-series. As noted by Blaas et al., arrowheads distort the perception of a continuous spline. They therefore opted for a texture-based approach that uses animated dash patterns to visualize edge direction. They are furthermore planning to continue their investigation into the visualization of directed edges using animated textures.

Animated links have also recently been added to the wellknown Tulip graph visualization library [START_REF] Auber | Tulip: A Huge Graph Visualisation Framework[END_REF]. The dash patterns used by Tulip move along a straight line from start to end and are made up of repeating "greater than" (" ") symbols depicted using alternating colors.

Evaluation

Apart from the initial study [START_REF] Holten | A User Study on Visualizing Directed Edges in Graphs[END_REF] that inspired our work, only few user studies have been performed to quantify how directed-edge representations perform in the context of nodelink graphs. One of these is the user study performed by Wong et al. for their GreenArrow approach. However, their focus was on how to balance the appearance of a graph and its labels, not on determining how well their approach works as a technique for depicting directed edges in comparison with other directed-edge representations.

An additional motivation for our follow-up evaluation of the performance of directed-edge representations is the remark of Kosara et al. [START_REF] Kosara | Thoughts on User Studies: Why, How, and When[END_REF], who note that visualization as currently practiced is mostly a craft and evaluation is often only performed informally. Because of this, user studies in visual-ization should be encouraged. This is further supported by North [START_REF] North | Toward Measuring Visualization Insight[END_REF], who also states that there are too many informal usability studies that only indicate whether or not a small number of users like a certain visualization technique. Visualization evaluation should seek to quantifiably determine how well visualizations perform, and one way of doing this is to perform controlled user studies.

Graphs and Directed-Edge Representations

This section provides details on the choices that were made with regard to the generative graph model, the graph layout, the directed-edge representations, and the way in which node pairs were chosen during trials to ensure controlled testing of different link lengths.

Graph Model

To ensure the availability of enough different graphs with similar statistical properties for all of the participants and for all of the combinations of graph density, edge representation, and link length, we chose to generate random graphs using a graph generation model. The graph model used in the initial study was proposed by Ware et al. [START_REF] Ware | Supporting Visual Queries on Medium-Sized Node-Link Diagrams[END_REF][START_REF] Ware | Visualizing Graphs in Three Dimensions[END_REF]. It generates graphs as follows: "For each graph node, form a directed edge to one or two other nodes, randomly selected, so that a single connection occurs p% of the time and two connections occur (100 -p%) of the time," where p controls the density. This model is more suited for real-world graphs than the model by Erdős et al. [START_REF] Erdős | On Random Graphs[END_REF], who define a random graph as G(n, p) in which each of the n 2 possible edges occurs with probability p. However, the node-degree distribution of the Ware-et-al.-graphs does not follow a power law (is not scale-free), i.e., the fraction P (k) of nodes having k connections to other nodes is not modeled by P (k) ∼ k -γ , typically with 2 < γ < 3. Many empirically observed networks, however, do appear to be scale-free, including social, citation, and protein networks.

We therefore chose a graph generation model that produces scale-free (small-world) graphs, i.e., graphs with a power law distribution, such as the Barabási-Albert (BA) [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF] or the Watts-Strogatz [START_REF] Watts | Collective Dynamics of Small-World Networks[END_REF] model. We used the Network Workbench [START_REF] Nwb Team | Network Workbench Tool (Network Workbench: A Large-Scale Network Analysis, Modeling and Visualization Toolkit for Biomedical[END_REF], a network analysis, modeling, and visualization toolkit, to auto-

Graph Layout

There are many node-link-graph layout models available, the majority of which make use of force-directed node placement algorithms (or adaptations thereof), such as Eades' springembedder model [START_REF] Eades | A Heuristic for Graph Drawing[END_REF], the Kamada-Kawai [START_REF] Kamada | An Algorithm for Drawing General Undirected Graphs[END_REF] model, or the Fruchterman-Reingold [START_REF] Fruchterman | Graph Drawing by Force-Directed Placement[END_REF] model.

Due to its real-world popularity, ease of implementation, and overall good results for graphs up to a couple hundred nodes, we chose the Fruchterman-Reingold (FR) algorithm to lay out our graphs. All layouts were generated by a JUNGbased [START_REF] Madadhain | Analysis and Visualization of Network Data Using JUNG[END_REF] FR implementation as provided by the GUESS graph exploration system [START_REF] Adar | GUESS: A Language and Interface for Graph Exploration[END_REF] from within the Network Workbench (see Figure 1).

Directed-Edge Representations

Many feasible directed-edge representations remain to be comparatively evaluated. We chose to evaluate the performance of three representations that seemed particularly promising based on previous work. Specifically we evaluated 1) tapered, the best representation according to the initial study, 2) an animated representation, and 3) a representation that uses biased clockwise curvature as proposed by Fekete et al. [START_REF] Fekete | Overlaying Graph Links on Treemaps[END_REF]. This biased-curvature-based representation might be a better alternative than the non-biased representation evaluated in the initial study. Based on information directly provided by Holten, Van Wijk, and Fekete, we modeled all representations to adhere to their original design and to be similar to the representations used in the initial study.

We used a 23" LCD display with a 16:10 width:height ratio and a native resolution of 1680×1050 pixels to represent all of our graphs at 4× anti-aliasing on a white background. All visualizations were generated within our OpenGL-based evaluation tool, which was written in Borland Delphi. Given the display diagonal and the resolution, our display provided approximately 86 DPI.

The tapered representation was similar to the one used in the initial study: 4.31px (0.05") wide at the start, 0.43px (0.005") wide at the end, and drawn in black at an opacity of 35% (see Figure 2a).

Based on information directly provided by Fekete, we modeled the biased-curvature representation as a quadratic Bézier curve defined by the points A, B, and C as shown in Figure 2b; Point B is generated by 90 • counterclockwise rotation of the midpoint of A and C around A. The curve is drawn at 1.29px (0.015") wide in black at an opacity of 40%. We used a higher opacity than tapered to compensate for the fact that -due to its thinner design -it covers less display area.

Finally, the animated representation used a moving dash pattern with a cycle length of 30px (0.35"), 90% of which, i.e., 27px (0.31"), was occupied by a line, and 10% of which, i.e., 3px (0.04"), was occupied by a gap (see Figure 2c). The pattern moved along a straight line from start to end at a speed of 15px (0.17") per second. Each animated link used a different, randomly assigned phase to prevent distracting "bursts" of activity caused by multiple incoming/outgoing links around a node. The animated links were also drawn in black at an opacity of 40% using a line width of 1.29px (0.015").

Although our texture-based animation model is capable of generating more complex animated links using gradient-based patterns with smoothly varying colors and opacity, we chose the aforementioned settings to prevent the animated representation from claiming visual attributes such as (varying) color, opacity, and line width that can be used to encode other attributes in addition to directionality. The exact settings for our candidate representation were determined using pilot runs that assessed the length, density, and speed of the dash patterns that the majority of the participants felt comfortable with. Figure 3 shows an identical region of a medium-density graph using each of the three directed-edge representations.

Link-Length Selection

For each path-readability trial (see Section 4.4 for a detailed task description), a pair of start and end nodes A and B was selected between which a directed link L might be present. Since difficulties caused by visual clutter and overlap occur more often in the central region of a force-directed graph layout, we ensured the selection of node pairs from the central part of the graph layout. This was done by calculating a bounding circle for each graph layout and adding a normalized, cut-off 2D Gaussian on top of this with a value of 1 To select a short, medium-length, or long link for a trial (see Figure 4 for examples), the minimum-and maximumlength links L min and L max were first determined. Based on the range D = L max -L min , the links were sorted from short to long and divided into three bins, i.e.,

B short = [L min , L min + 1 3 D , B medium = [L min + 1 3 D, L min + 2 3 D , and B long = [L min + 2 3 D, L max ].
To determine the probability of a randomly chosen link from Bin B (a certain length class) getting accepted, 1D normalized, cut-off Gaussian was centered on the median-length link in B, having a value of 1 at the center and 0 (at 3σ) at the bin boundaries. The probability of a randomly chosen link in Bin B getting accepted is

P B (L) ∈ [0, 1].
Taking the position of a link with respect to the graph center into account, the combined probability of a randomly chosen link in Bin B getting accepted now becomes

P center (L A , L B ) • P B (L) = P (L) ∈ [0, 1],
where L A and L B are the start and end nodes of Link L, respectively.

Experiment -Comparing Directed-Edge Representations

As previously stated, the goal of our experiment was to extend previous work on the readability of directed edges. We chose to evaluate tapered, the best directed-edge representa-tion based on the results of an initial study [START_REF] Holten | A User Study on Visualizing Directed Edges in Graphs[END_REF], and added two new ones: animation and biased curvature (henceforth called "biased"). In addition, we tested three graph densities and three link lengths.

Hypotheses

Based on the results of previous work, we hypothesized that overall, tapered links would outperform the other two in this experiment as well (H1). However, we hypothesized that interaction effects would be present for the different graph densities and link lengths (H2). In terms of interaction effects we specifically had the following hypotheses:

H3: For sparse graphs, tapered will outperform the other two representations due to minimal overlap and its strong indication of direction; H4: For dense graphs, tapered will perform worse than the other two representations due to its increased use of "ink" (display area); H5: For long links, biased will perform significantly worse than the other two representations due to increased edge overlap.

We were unsure how the animated links would perform. Animation has a strong perceptual focus and may lead to increased visual clutter of the graph. On the other hand, the strong perceptual cues provided by animation may lead to an increased ability to follow links. We were further unsure how tapered and animated links would compare for long edges.

Design

We used a repeated-measures design with the following within-subjects independent variables: edge representation (tapered, biased, animated), graph density (sparse, medium density, dense), and link length (short, medium length, long). Each participant performed 10 repetitions of trials, each repetition containing 27 trials. The order of combinations of graph density, link length, and edge representation was randomized per repetition of trials. Before each repetition of trials, participants were allowed to rest and could continue to the next repetition whenever they were ready. Experimental sessions lasted about 30 minutes including training. In summary, the design included: The dependent variables that we measured are reading time and correctness on a per-trial basis. In addition, we analyzed qualitative feedback from the post-study questionnaire.

Participants and Procedure

Twenty-seven participants (15 male, 12 female) were recruited from two research institutions. They ranged in age from 22 to 58 years (median 30 years). All participants had normal or corrected-to-normal vision and were tested for colorblindness. Seven participants reported looking at node-link graphs at least weekly, 13 participants reported monthly or yearly exposure, and six reported to be unfamiliar with nodelink-graph representations. Eleven participants were students and 16 were non-students with varying technical as well as non-technical occupations, e.g., nurse, administrator, or researcher. Participants were not paid for their involvement in the study.

Participants were seated in front of a Dell LCD display at a viewing distance of approximately 50cm; subsection 3.3 includes further details on the display settings. Participants were first given a short introduction to node-link graphs and the different types of edge representations used in the study. The experimenter then described the task, how to step through the trials, and how to record an answer. Participants answered by pressing the "0" (no directed connection present) and "Enter" (directed connection present) keys on the keyboard and they pressed the "Space" key to start a new repetition of trials. Participants first conducted 50 practice trials to ensure that they were familiar with how to read the edge representations and with the experimental setup and procedure. After the practice trials, participants were asked if they had any further questions. If not, they continued to the experiment. After the experiment, participants filled out a post-session questionnaire to elicit qualitative feedback and demographic information.

Tasks

We used a path-readability task in which participants had to answer the following question throughout the study: "Is it possible to go from the green node to the orange node in exactly one step?" This task was chosen as it tests local readability of node connections and gives an indication of how well the chosen edge representation allows participants to infer directionality. Participants were instructed to be both as accurate and fast as possible. The correctness of their answer was shown to participants only during practice trials (immediately after a trial) and not during the actual experiment.

Each trial was shown to participants full-screen in three stages. During the first stage participants saw an empty white screen for 400ms. During the second stage we showed two randomly selected nodes A (green) and B (orange) to the participants for 600ms. This stage was introduced to ensure that participants did not spend time finding the two nodes in the graph. Finally, in stage three the complete graph (with A and B in the same positions) was displayed and timing for the trial was started.

A legend for the currently used edge representation was displayed in the lower-left corner of the screen (see Figure 5). Participants were presented with a new graph for each trial and Nodes A and B were chosen such that there was a 50% chance of a connection being present; in 50% of the cases in which a connection was present, the connection also had the correct direction, i.e., there was a 25% overall chance of a connection being present and having the correct direction (from A to B). The chance of a bidirectional connection being present was not explicitly controlled for. The randomly selected graphs were generated and laid out as discussed in Sections 3.1 and 3.2 and link lengths were selected as discussed in Section 3.4.

Results

The completion times collected during the experiment were first log-transformed to comply with the normality assumption of the data analysis. Then time was analyzed using a repeated-measures ANOVA. Timing data was recorded and analyzed at millisecond scale; average task times are reported here at second scale. The error data was analyzed using the non-parametric Friedman analysis of variance by ranks and Wilcoxon signed rank tests as the error data did not conform to the normality assumption.

Overall Effect of Edge Representation

There was a significant effect of edge representation on overall task completion time (F (2, 52) = 75.315; p < .001) with mean times diminishing from 1.81s (SD = 1.48) for tapered, to 1.92s (SD = 1.2) for animated, and 2.72s (SD = 2.25) for biased (see Figure 6). Post-hoc pairwise comparisons only showed a significant difference between biased and the two other representation with p < .001 in both cases.

Overall, participants made errors in only 6% of the trials. However, a Friedman analysis showed a significant effect of edge representation on the correctness of the trials (χ 2 (2) = 29.16; p < .001) with errors increasing from 101 for tapered, to 102 for animated, and 248 for biased links out of 2,430 trials per edge representation (see Figure 7). Wilcoxon signed rank tests again only showed a significant effect between biased and the two other representations, with Z = -4.12 for comparison to animated, Z = -4.05 for comparison to tapered, and p < .001 in both cases. We, thus, confirmed our first hypothesis (H1), that tapered would perform well overall, but found animated to be a competitive alternative.

Biased

Effects of Graph Density

Tests showed a significant effect of graph density on task completion time (F (2, 52) = 54.56; p < .001) with average times of 1.97s (SD = 1.24) for sparse graphs, 2.13s (SD = 1.39) for medium-density graphs, and 2.34s (SD = 1.59) for dense graphs. Post-hoc pairwise comparisons showed a significant effect between all graph densities with p < .001 each. Error analysis showed a significant effect between the three densities (χ 2 (2) = 10.65; p < .005). Post-hoc pairwise comparisons showed a significant difference for medium-density and dense p < .002 as well as sparse and dense graphs p < .001.

Although the difference between sparse and medium-density graphs was not significant, the other differences indicate that there is a monotonic increase in error. This analysis confirms that we chose an appropriate increase in density for the graphs. Next, we looked at the effect of graph density with respect to the three different edge representations. The analysis of task completion time showed a significant effect for edge representation × graph density (F (4, 104) = 3.535; p < .002). Post-hoc comparisons showed a significant difference between biased and tapered as well as biased and animated representations for all three graph densities (p < .001 in each case). No significant difference was observed between tapered and animated links for any of the graph densities. Figure 8 gives an overview of the average trial times observed for each edge representation and graph density.

During the analysis of trial errors we observed the same pattern.

An overall significant difference for edge representation × graph density (χ 2 (8) = 46.76; p < .001) emerged. Further cross-comparisons per type of graph density showed significant differences between the biased representation and the two other ones. Similar to the analysis of trial time, no significant difference was observed between tapered and animated links. Table 1: Significant differences for cross comparisons according to trial error for animated (A), biased (B), and tapered (T) links in sparse, medium-density, and dense graphs.

Thus, we partially confirmed our third hypothesis (H3). Tapered performed well in sparse graphs but there was no significant difference in trial time or error to animated links. We did not, however, confirm H4. Against our initial hypothesis, tapered links performed well for dense graphs as well, and again we did not show a difference to animated links. Biased links performed the worst according to both time and error.

Effects of Link Length

Tests showed a significant effect of link length on task completion time (F (2, 52) = 105.26; p < .001) with average task completion times of 1.95s (SD = 1.37) for short links, 2.09s (SD = 1.4) for medium-length links, and 2.4s (SD = 1.43) for long links. Post-hoc pairwise comparisons showed a significant effect between each of the three lengths with p < .001 in each case. No significant effect was observed between link lengths in terms of correctness. Participants were 94.2% correct with short links, 94.4% correct for medium-length links, and 92.9% correct with long links. Although the differences in error rate were not significant for the different link lengths, the timing information shows that participants spent significantly longer for trials with longer links indicating an increase in difficulty.

Next we analyzed interaction effects for edge representation × link length. The analysis of task time showed a significant difference between the three lengths and representation types (F (4, 104) = 4.48; p < .002). Posthoc comparisons showed significant differences between the biased representation and the two other ones with p < .001 in each case. For short and long links the data exhibited no significant difference between tapered and animated links. Only for medium-length links, a significant difference (p < .022) occurred for those two representations with tapered being significantly faster at 1.69s on average than animated at 1.86s on average. Figure 9 gives an overview of the average trial time for each edge representation separated by the three link lengths.

The Friedman analysis of variance showed a significant effect of error rate for edge representation × link length (χ 2 (8) = 57.46; p < .001). Cross-comparisons by link lengths showed no significant difference in errors among the three representations for short links. For medium-length and long links, the data exhibited a significant effect between the animated and biased as well as biased and tapered representations, but not between tapered and animated. Table 2 gives an overview of the relevant significance scores for these tests.

In summary, we saw interaction effects for edge representation for both density and length, confirming our second hypothesis (H2). We could confirm H5 as biased links performed significantly worse than the others for long links. However, it should be noted that it in fact performed significantly worse than the other two techniques for all link lengths.

Qualitative Feedback

The post-session questionnaire elicited feedback from participants on their subjective preferences and ratings for the three edge representations.

General Preference

Two participants chose the biased representation as their overall favorite, eleven chose the animated type, and the remaining fourteen participants preferred the tapered representation. Figure 10 gives an overview of participants' preferences. The reasons participants gave for choosing animated or tapered as opposed to the biased representation were fairly similar. Participants found them to be "intuitive" (two responses each for tapered (2-T) and animated (2-A)), preferred the direct connection in comparison to the biased representation (3-T; 5-A), named them "easier to follow" (4-T, 1-A), faster (1-T, 1-A), and thought that those two representations produced minimal clutter (2-T, 3-A). Not all participants produced an answer to why they preferred a specific representation and some named several reasons, therefore the answer numbers to this question do not represent the total number of participants. Some participants further explained why they preferred a specific representation. Participants saw an advantage of the tapered links in that the varying width allowed them to more easily infer whether a node intersecting a link was a start or end node. Participants also reported that biased links were difficult to follow in dense situations as the angle of the curve was hard to guess and had to be searched for. Participants further stated that whether a connection was present or not was easy to see for both tapered and animated but not for biased links. One participant was also concerned that animated links would imply variations or flow over time (such as the movement of people between cities), which may not always properly represent the semantics of a link in a graph.

Preference by Graph Density and Link Length

Participants were further asked to rank the techniques for each graph density they encountered. Overall, biased was the first choice for each graph density only five times or less. Animated and tapered links were chosen equally often for dense graphs.

For medium-density graphs, animated links were the number one choice of most participants: they were chosen fourteen times compared to ten times for tapered links. Participants showed a clear preference for tapered links for sparse graphs, however: they were ranked first sixteen times compared to 7 times for animated links. Figure 11 gives an overview of which edge representation participants rated first for each graph density. Furthermore, participants were asked to rank the edge representations for the two extreme link lengths: short and long links. As the experiment randomly presented participants with different link lengths, medium-length links were excluded from this question. For short links, the tapered representation was the most preferred, while animated links were the most preferred technique for long links (Figure 12). Together with the analysis of graph density, participants tended to prefer tapered links for sparse graphs and short, animated links for longer links and medium-density graphs; they were equally effective with both in the quantitative evaluation.

Self-Rated Speed and Correctness per Representation

To capture possible differences in actual and perceived efficiency and effectiveness with a given edge representation, participants were asked to rank their perceived correctness and speed on a 7-point Likert scale. The scale ranged from 1: strongly disagree to 7: strongly agree. Table 3 summarizes the answers to these questions. Reflecting the results of the quantitative measurements, participants were least sure about their performance with the biased representation. The answers to perceived speed and correctness for both animated and tapered were again significantly different to the biased representation (p < .001 for speed and p < .007 for correctness) but not significantly different between animated and tapered.

Aesthetics

Participants were further asked to rate the three representations on their ability to produce "nice-looking graphs." Participants rated the biased representation with a median of 4 (no opinion, mean = 4.15), tapered with a median of 5 (somewhat agree, mean = 5.22), and animated also with a median of 5 (mean = 5.15). While the difference in rank of the biased link to the two other representations was smaller for this question compared to previous ones, there was still a significant difference to the two other techniques with p < .022; Z = -2.29 compared to tapered and p < .034; Z = -2.12 compared to animated. No significant difference between the ratings for tapered and animated links was observed.

Discussion

The quantitative results are consistent with the self-rated perception of the participants. From the experiment, the biased representation is always less effective than the two others and is also the least preferred. Therefore, it should probably not be used if any of the two others is an option. The animated representation is effective, even competing with the tapered representation on almost all the conditions except for medium-length links. The reason why this condition is different from the others needs further study; so far, we have no explanation. Since tapered links were more effective than all the others tested in the initial study [START_REF] Holten | A User Study on Visualizing Directed Edges in Graphs[END_REF], we expect animated links to also be more effective.

We can now choose the link representation of a node-link diagram in a more rational way than before. There are still tradeoffs to keep in mind. One tradeoff concerns the visual attributes that can be used along with the representation. For example, tapered links require transparency and a varying thickness to be readable. If changing the link thickness or transparency according to an edge attribute is important, tapered links cannot be used or could become less effective. Animated links, on the other hand, can support varying thickness and variation of transparency but cannot be used on paper or any static medium. Further research is also required to test different types of animation patterns for screen use. We proposed one that tested very well in comparison to tapered but many different patterns are possible and may not support path readability in the same way (they may be better or worse).

As another tradeoff, animated links are more complex to program and require more graphics performance to work smoothly on large graphs. Finally, edge routing or bundling cannot be used with biased links because the shape of the curve is constrained by the routing itself.

To summarize: tapered links were always good and should be preferred by default, unless link thickness or transparency should vary. Animated links can be used in that case. Finally, tapered and animated links can likely be combined or used to differentiate categorical attributes of links with up to three values: tapered, animated and tapered-animated.

Conclusion

In this article, we have reported on a controlled experiment comparing the readability of three directed-edge representations for node-link diagrams: tapered, biased, and animated. The study used graphs randomly generated using the Barabàsi-Albert model and laid out using the Fruchterman-Reingold algorithm. The factors were the three edge representations, the density of the graphs (sparse, medium density, and dense) and the link lengths (short, medium length, and long). We tested one low-level connectivity task: showing two nodes, asking if the first node was connected to the second. We collected the time to complete and the number of errors, as well as a user questionnaire eliciting subjective feedback from participants.

The study showed that tapered and animated links were always faster to read and more accurate than the biased-link representation. Tapered was significantly faster than animated for only one condition: medium-length links. The questionnaire reported consistent conclusions regarding user preferences and self-assessment.

From this study and the initial one, we can conclude that the best directed-edge representation for the readability task is tapered, followed by animated. We also provide advice and recommendations in the discussion section for choosing a representation according to various constraints and tradeoffs.

This study revealed that animated links were effective at depicting directed edges, matching the best technique in most conditions. The participants provided interesting reasons explaining why tapered links are still better in some cases: when a link crosses a node but does not end, the thickness of the tapered link allows one to resolve the ambiguity while animated links remain ambiguous.

Future Work

The design space of animated links is large and we have only tried a very simples design so far. Given the user feedback, we need to improve the design of animated links to disambiguate between crossings and end points. We should also try to find the optimal parameters in terms of dash sizes and speed, or vary the shape of the moving part using glyphs or other patterns.

Now that we have evaluation results from several types of link representations, we can also study how to combine them either as visual attributes for categorical attributes or to visualize overlapping edges that have identical start and end points. Another possibility is to combine different representations in dense or sparse graph regions or to differentiate short and long links.

We have only tested edge representations for one task. There are, or course, several other tasks involved in graph visualization and the results of the representations we have tested are likely to be different for some of them. For example, tapered and biased links provide an easy assessment of the overall link length (the thickness variation of the tapered link, the derivative of the curve of the biased link). Higher-level tasks could also benefit from different edge representations but have not yet been formally tested.

Figure 1 :

 1 Figure 1: From left to right: a sparse (60 nodes), medium-density (90 nodes), and dense (135 nodes) graph as used during the experimental trials. The graphs were generated using the Barabási-Albert [3] scale-free model and laid out using the Fruchterman-Reingold [10] algorithm.

Figure 2 :

 2 Figure 2: The directed-edge representations that were evaluated: (a) tapered from wide (start) to narrow (end), (b) biased clockwise curvature from high (start) to low (end) curvature, and (c) animated, in which a pattern moves from start to end along a straight line.

Figure 3 :

 3 Figure 3: Identical regions of a medium-density graph shown using a (a) tapered, (b) biased, and (c) animated representation.

Figure 4 : 2 -

 42 Figure 4: A medium-density, undirected graph in which representative links for each link-length class are highlighted using red (short), green (medium length), and blue (long).

Figure 5 :

 5 Figure 5: Example view of a trial as presented to participants. Task instructions resided in the top-left corner (1), the graph in the screen center (2), and a legend on how to read the directed-edge representation in the lower-left corner[START_REF] Becker | Visualizing Network Data[END_REF]. Test nodes were highlighted in green for the start node (3) and orange for the end node (4).

Figure 6 :Figure 7 :

 67 Figure 6: Average completion time per representation.

Figure 8 :

 8 Figure 8: Average trial time per representation by graph density. Sparse Medium Density Dense A-B T-B A-B T-B A-B T-B Z -3.0 -2.61 -3.06 -3.05 -3.67 -3.36 p < .003 < .009 < .002 < .002 < .001 < .001

Figure 10 :

 10 Figure 10: Participant-preferred representation type.

Figure 11 :Figure 12 :

 1112 Figure 11: Participants' first choice of technique by graph density.

  Table 1 gives an overview of the respective significance values.

				Biased		Tapered			Animated
				3,063
		3000
				2,652
		2500	2,429
	Average Time (ms)	1000 1500 2000			1,707	1,769	1,969	1,787	1,970	1,990
		500
		0
			Sparse	Medium Dense	Sparse	Medium Dense	Sparse	Medium Dense

Table 2 :

 2 Average trial time per representation by link length. Significant differences for cross comparisons according to trial error for animated (A), biased (B), and tapered (T) links with medium-length and long links.

			Biased			Tapered		Animated
		3000		2,728	3,004
		2500	2,412
	Average Time (ms)	1000 1500 2000				1,668	1,694	2,083	1,767	1,856	2,124
		500
		0
			Short Medium Long	Short Medium Long	Short Medium Long
		Figure 9: Medium Length		Long
					A-B	T-B	A-B	T-B
			Z	-3.97	-3.59	-4.08	-3.89
			p	< .001 < .001 < .001 < .001

Table 3 :

 3 Results of the Likert-scale questions: "The technique allowed me to be (fast/correct)."

Acknowledgements

We would like to thank all of the participants in our study for their time. This project is partly funded by the Netherlands Organization for Scientific Research (NWO) View programme under research grant no. 638.100.502 (Expression of Interest Project).


Siegfried Benkner

Enes Bajrovic

Erich Marth

Martin Sandrieser

Raymond Namyst

Samuel Thibault

High-Level Support for Pipeline Parallelism on Many-Core Architectures

With the increasing architectural diversity of many-core architectures the challenges of parallel programming and code portability will sharply rise. The EU project PEPPHER addresses these issues with a component-based approach to application development on top of a taskparallel execution model. Central to this approach are multi-architectural components which encapsulate different implementation variants of application functionality tailored for different core types. An intelligent runtime system selects and dynamically schedules component implementation variants for efficient parallel execution on heterogeneous many-core architectures. On top of this model we have developed language, compiler and runtime support for a specific class of applications that can be expressed using the pipeline pattern. We propose C/C++ language annotations for specifying pipeline patterns and describe the associated compilation and runtime infrastructure. Experimental results indicate that with our high-level approach performance comparable to manual parallelization can be achieved.

Introduction

With the shift towards heterogeneous many-core architectures combining different types of execution units like conventional CPU cores, GPUs and other accelerators, the challenges of parallel programming will sharply rise. For an efficient utilization of such architectures usually different programming models and APIs, tailored for the different types of execution units, have to be combined within a single parallel application. Available technologies like Intel TBB [START_REF] Intel | Threading Building Blocks[END_REF], CUDA [START_REF] Nvidia | Compute Unified Device Architecture Programming Guide[END_REF], Cell SDK [START_REF] Kahle | Introduction to the Cell Multiprocessor[END_REF], and OpenCL [START_REF]OpenCL 1.0 Specification[END_REF] are characterized by a low level of abstraction, forcing programmers to take into account a myriad of architecture details, usually beyond the capabilities of average users. Several recent research projects including ParLab [START_REF] Pan | Composing Parallel Software Efficiently with Lithe[END_REF], PetaBricks [START_REF] Ansel | PetaBricks: A Language and Compiler for Algorithmic Choice[END_REF], Elastic Computing [START_REF] Wernsing | Elastic Computing: A Framework for Transparent, Portable, and Adaptive Multi-core Heterogeneous Computing[END_REF], ENCORE [START_REF] Vandierendonck | Parallel Programming of General-Purpose Programs using Task-based Programming Models[END_REF] and others, are addressing these challenges by proposing higher-level programming support for emerging many-core systems.

The European research project PEPPHER [START_REF] Benkner | PEPPHER: Efficient and Productive Usage of Hybrid Computing Systems[END_REF] targets programmability and performance portability for single-node heterogeneous many-core architectures by means of a component-based approach in combination with a task-parallel execution model. In this paper we present our contributions towards high-level support for pipelined applications within the PEPPHER framework. Section 2 outlines the PEPPHER approach and describes the proposed language features for realizing pipelined C/C++ applications. Section 3 describes our source-tosource transformation framework as well as the coordination and runtime support for pipelining. Experimental results for two real-world applications and a comparison to TBB are presented in Section 4. The paper closes with a discussion of related work and future directions.

High-Level Programming Support

Since there exists no parallel programming model that covers all types of parallel applications and architectures, we argue that a programming framework for heterogeneous parallel architectures should support the use of different programming models and APIs within an application.

The PEPPHER Component Model

Within the PEPPHER model performance-critical parts of an application are realized by means of multi-architectural components that encapsulate, behind an interface, different implementation variants of a function3 tailored for different execution units of a heterogeneous many-core system.

Component implementation variants are usually written by expert programmers using different programming APIs (e.g., CUDA, OpenCL) or are taken from optimized vendor-supplied libraries. Non-expert programmers may then construct applications at a high level of abstraction by invoking component functionality using conventional interfaces and source code annotations to delineate asynchronous (or synchronous) component calls. With this approach, a sequential program spawns component calls, which are then scheduled for task-parallel execution by the runtime system. A source-to-source compiler transforms annotated component calls such that they are registered with the runtime system and generates corresponding glue-code.

The compiler and runtime system make use of rich component meta-data, usually supplied by expert programmers via external XML descriptors. Besides information about the data read and written by components, meta-data includes information about resource requirements, possible target platforms, and performance relevant parameters [START_REF] Sandrieser | Using explicit platform descriptions to support programming of heterogeneous many-core systems[END_REF]. The runtime system, built on top of the StarPU [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF] heterogeneous runtime system, relies on a representation of the program as a directed acyclic graph (DAG) where nodes represent component calls (tasks) and edges represent data dependences. The runtime system dynamically schedules component calls to the available execution units of a heterogeneous many-core architecture such that (1) independent component calls execute in parallel on different execution units and (2) the "best" implementation variants for a given architecture are selected based on historical performance information captured in performance models.

Language Support for Expressing Pipeline Patterns

A pipeline consists of several inter-connected stages, where a stream of data flowing through the pipeline is processed at every stage. Data entering a stage via input port(s) is consumed, processed and emitted at the output port(s) accordingly. Usually, stages are connected via buffer structures from which data is fed into stages. While buffered pipelines require additional memory, they allow to decouple stages and mitigate relative performance differences. In our approach buffers between stages are generated automatically, but we provide language features for the user to control certain aspects of buffering.

The pipeline pattern has the potential of exploiting two levels of parallelism: inter-stage parallelism, if different stages execute on different cores, and, intrastage parallelism, if a stage is itself parallel and executes on, e.g., a GPU.

In our framework, pipelines may be constructed from while loops where the loop body comprises two or more calls to multi-architectural components as considered within the PEPPHER framework. The pipeline pragma indicates that the subsequent while loop represents a pipeline. Each stage of the pipeline corresponds to a single component call statement within the loop body.

Stage Replication and Stage Merging

Provided application logic permits, stage replication aims to increase the potential parallelism of pipelined applications by creating multiple replicas of a stage that may then be executed in parallel. Stages can be replicated using the stage pragma with the replicate(N) clause, specifying that a stage should be replicated N times (see Listing 1.1). As a consequence, multiple stage instances will be generated by the compiler to enable processing of different data packets in parallel, if enough execution units are available. While replication is a suitable technique for increasing pipeline throughput by replicating stages with (relative) high execution times, the programmer has to be aware that the order in which data-packets are processed may change (unless priority ordering is used), resulting in unpredictable application behavior. Moreover, sizes of connected in-and output buffers may have to be adapted as well. Also, stage replication might result in a performance degradation if not enough execution units are available to execute all stage replicas in parallel.

The stage pragma may also be used to merge multiple stages into a single stage (see, e.g., Listing 1.4). This allows the programmer to manually increase the granularity of stages, if the involved individual component calls do not exhibit enough computational density to mandate processing within a separate stage. Note that stages can only be merged if for all involved stages compatible component implementation variants are available. The interface of the resulting single stage is automatically generated by the compiler, describing all input and output ports of the merged stage.

Buffer Management

With our framework buffers are automatically generated in between pipeline stages. These buffers temporarily store data packets, generated by the source stage(s), and consumed by the target stage(s). Depending on the type of application, different order guarantees and sizes for buffers may be required. Therefore we provide the buffer clause for specifying the order guarantee, including priority, random, and fifo, as well as the size of buffers (see Listing 1.2). Global buffer settings may be specified by using the with buffer clause together with the pipeline pragma. Local buffer settings for individual stages may be specified with the buffer for port clause within the stage pragma. In Listing 1.2 the buffer for port cdata in the second stage is changed to RANDOM and buffer size to 8, while for all other buffers FIFO ordering is used.

Implementation

We have developed a prototype source-to-source compiler that transforms C/C++ applications with the described annotations into C++ with calls to a pipeline coordination layer that utilizes the StarPU [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF] heterogeneous runtime system for scheduling stages for parallel execution onto the execution units of a heterogeneous many-core system comprising CPUs as well as GPUs. The source-to-source compiler has been implemented using the ROSE compiler infrastructure [START_REF] Quinlan | ROSE: Compiler Support for Object-Oriented Frameworks[END_REF].

Source-To-Source Transformation

After the usual front-end processing phases an abstract syntax tree is constructed. Pipeline constructs are then further processed to determine the structure of the pipeline (stage interconnection) by analyzing the data types of objects passed between pipeline stages. For each stage interconnection (port) corresponding buffer structures, as specified globally or locally, are generated.

The generated target code contains calls to the pipeline coordination layer which comprises various classes for coordinating the execution of pipeline stages on top of the StarPU runtime system. on the stage functionality (component), directly connected buffers and stages for each port, the number of instances of a stage to be processed in parallel (replication count), and the position of the stage within the pipeline (source, inter, or sink ). Each stage owns a local coordination mechanism, described later, which slightly differs depending on the position of a stage. The abstract Buffer class generalizes the buffer access interface and is used to derive concrete buffer implementations like FIFO buffers or priority buffers. Each buffer stores information about connected stages, internal storage layout, and the type of data packets.

Figure 1 gives an overview for a three-stage data compression pipeline example. First buffer objects are generated (line 1) for holding data packets and meta-data such as priority tags, creation dates, and other information. Next, all inter-stage buffers are generated to hold the previously generated buffer objects, setting the default data type for each buffer, as shown in line 2. Class instances for the read and compress stages are generated in line 3 and 4. The stages are further configured by specifying connected buffers, replication counts, and the stage computations, as shown in line 5 to 8. After all stages have been created and configured, stages are posted for execution to the runtime, initiating the actual execution of the pipeline, as shown in line 9.

Task-based Heterogeneous Runtime

The StarPU runtime system [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF] utilized in our framework is based on an abstraction of the underlying heterogeneous many-core architecture as a set of workers, each representing either a general purpose computing core, or an accelerator (e.g., a GPU). The runtime system is responsible for selecting suitable component implementation variants for pipeline stages and for scheduling their execution to workers in a performance-and resource-efficient way, according to a specific scheduling policy. StarPU manages data transfers between workers, ensures memory coherency, and provides support for different scheduling strategies which may be selected at runtime.

The scheduling policy used within this paper is the Heterogeneous Earliest Finish Time [START_REF] Topcuoglu | Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing[END_REF] policy. This policy considers inter-component data dependencies, and schedules components to workers taking into account the current system load, available component implementation variants, and historical execution profiles, with the goal of minimizing overall execution time by favoring implementations variants with the lowest expected execution time.

Coordination

The coordination layer controls the execution of a pipelined application by deciding when to post stage component calls to the runtime system. We utilize a local coordination strategy where each stage is at runtime controlled by a corresponding stage object (an instance of the Stage class). The Stage class provides two methods for coordinating the execution of a pipelined application: the method execute() for posting a stage for execution to the runtime system and the method callback() for transferring control back to a stage object after its associated component has finished execution on a worker. In the following we outline a coordination scenario for the code shown in Figure 1.

First the runtime system is initialized and the required stage and buffer objects are instantiated. Next, the execution of all stages is initiated by invoking the execute() method on each stage object. This method posts a stage for execution to the runtime system provided its input buffer(s) and free slots in its output buffer are available. In our scenario, initially only the read stage is posted to the runtime while execution of all other stages is postponed since no input data is yet available. The runtime system then selects a suitable component implementation variant for the read stage and schedules it for execution onto a worker. When the read stage finishes execution on the selected worker, the runtime system invokes its callback method. Within the callback, first all connected buffers of the read stage are updated and then the execute() method of the connected compress stage is called, which results in posting the compress stage to the runtime system. Finally, if a new data packet to be processed and a free output buffer slot are available, the read stage re-posts itself for execution to the runtime system. The runtime can now schedule the second instance of the read stage and the first instance of the compress stage for parallel execution on different workers. With this scheme, stages coordinate themselves only in combination with their immediate neighbors, but without a central coordinator.

Experimental Evaluation

An initial evaluation has been performed with two real world codes, a data compression application and a face detection application. We compare our approach to Threading Building Blocks (TBB) as well as to existing parallel implementations on two different architectures. Architecture A represents a homogeneous system with two Intel Xeon X7560 (8 cores, 2.26 GHz) running RHEL 5. Architecture B is a heterogeneous system with two Intel Xeon X5550 (4 cores, 2.67 GHz), one Nvidia GeForce GTX 480 (480 Cores, 1.5GB, 1.40GHz), and one Nvidia GeForce GTX 285 (240 Cores, 1GB, 1.48GHz), CUDA 4.0 and RHEL 5.6. The performance numbers shown are average execution times over ten runs.

BZIP2 Compression

BZIP2 is an open-source lossless data compression tool, based on the Burrows-Wheeler-Transformation [START_REF] Burrows | A Block-Sorting Lossless Data Compression Algorithm[END_REF]. Compared to other compression techniques, BZIP2 is embarrassingly parallel, compressing data at the granularity of blocks with a fixed size. Since there are currently no heterogeneous implementations available, BZIP2 cannot utilize the GPUs of architecture B.

Listing 1.3 outlines the implementation using our language constructs. We implement a three stage pipeline with FIFO and PRIORITY buffers and utilize the replication feature for the middle stage. For comparison, we have implemented bzip2 using the pipeline pattern of TBB to create a pipeline [START_REF]Intel Threading Building Blocks -Pipeline Documentation[END_REF] with three stages (read, compress, write) using the utility functions provided by the bzip2 library [START_REF] Seward | BZIP2 Library Utility Function Documentation[END_REF]. Since in TBB stages cannot be replicated explicitly, we have set the number of alive objects to twice the number of cores available. This allows TBB to schedule stages in parallel if possible. For correct compression in time, we have enabled order preservation. Moreover, we measured an existing code from the pbzip2 project [START_REF] Gilchrist | Parallel Data Compression with bzip2[END_REF], which represents a manually implemented pipeline with three stages (read, compress, and write) and priority buffers.

Table 1 shows the measured (average) execution times for the bzip2 benchmark for compressing a file with size of 1 GB. As can be seen, our high-level approach delivers performance results which are very similar to the other two approaches. However, the programming effort with our approach is significantly reduced, since our version requires only 80 lines of code, while pbzip2 comprises approx. 4000 lines of code and the TBB version 154 lines of code.

OpenCV Image Processing

The Open Source Computer Vision (OpenCV) library provides extensive support for the implementation of real time computer vision applications [START_REF] Gary | Learning openCV: Computer Vision with the openCV Library[END_REF]. Originally developed for homogeneous architectures, current releases offer built-in support for GPUs based on CUDA. Using OpenCV we have implemented a face detection application in a pipelined manner, where for the detection stage two different implementation variants, for CPUs and GPUs, are provided. Listing 1.4 sketches our implementation as a three-stage pipeline with priority buffers. The pipelines exits once 32 images have been processed. The middle stage, which merges two component calls, is replicated according to the available number of execution units within the system.

For comparison, a pipelined TBB version [START_REF]Intel Threading Building Blocks -Pipeline Documentation[END_REF] has been implemented in a similar way. Again, instead of stage replication, we have set the number of alive data packets to twice the number of execution units, enabling TBB to schedule stages in parallel. Table 2 shows performance results for the face detection code in comparison to the TBB version using different image resolutions including VGA(640x480), SVGA(800x600), XGA(1024x768), and QXGA(2048x1536). As can be seen, on architecture A our high-level approach outperforms the TBB version by about 20%. On architecture B, when using only the CPU cores, we get similar results. As opposed to TBB, however, our approach can take advantage of the GPUs by utilizing the GPU implementation variant for the (merged) middle pipeline stage. Since for each GPU an additional CPU core is required, the number of usable general purpose cores is reduced accordingly. As can be seen, using one CPU core and one GPU (GTX 460) the execution time is reduced by a factor of up to 3.14 compared to the TBB version using one CPU core. Using a second GPU results in only modest further performance improvements. Again the results show that our high-level approach to pipelining has the potential to outperform TBB, while significantly improving programmability. Moreover, based on our concept of multi-architectural components together with a versatile heterogeneous runtime system, we can take advantage of a heterogeneous CPU/GPU-based architecture without modifying the high-level application code.

Related Work

Over the last two decades design patterns as well as skeletons had a significant impact on software development in general as well as on parallel and distributed programming [START_REF] Benoit | Mapping Pipeline Skeletons onto Heterogeneous Platforms[END_REF][START_REF] Cole | Bringing Skeletons out of the Closet: A Pragmatic Manifesto for Skeletal Parallel Programming[END_REF][START_REF] Mattson | Patterns for Parallel Programming[END_REF][START_REF] Pop | A Stream-Computing Extension to OpenMP[END_REF].

Intel Threading Building Blocks (TBB) provides direct support for pipeline patterns. As opposed to our work, TBB targets only homogeneous architectures and does not support stage implementation variants.

Thies at al. [START_REF] Thies | StreamIt: A Language for Streaming Applications[END_REF] propose StreamIt, a domain specific language (DSL) for designing stream-based applications where in combination with the underlying compiler pipeline specific optimizations [START_REF] Sermulins | Cache Aware Optimization of Stream Programs[END_REF] are applied. However, support for heterogeneous architectures is not addressed in this work.

Schaefer at al. [START_REF] Schaefer | Engineering Parallel Applications with Tunable Architectures[END_REF][START_REF] Otto | A Language-Based Tuning Mechanism for Task and Pipeline Parallelism[END_REF], propose a language-based approach for engineering parallel application using tunable patterns. Although different stage implementations are supported within the pipeline pattern, support for heterogeneous architectures has not been addressed.

Suleman at al. [START_REF] Suleman | Feedback-Directed Pipeline Parallelism[END_REF], propose a feedback-directed approach with integrated support for tuning. In combination with online-monitoring, pipelined applications are optimized on a coarse-grain level. Neither different stage implementation variants, nor optimizations for heterogeneous architectures are supported.

There have been several proposals for extending C or Fortran in order to support programming of heterogeneous systems comprised of CPUs and GPUs including OmpSS [START_REF] Ayguadé | A Proposal to Extend the OpenMP Tasking Model for Heterogeneous Architectures[END_REF], PGI Accelerate [START_REF] Wolfe | Implementing the PGI Accelerator Model[END_REF], HMPP [START_REF] Bodin | Heterogeneous Multicore Parallel Programming for Graphics Processing Units[END_REF], and OpenACC [START_REF]OpenACC. Directives for Accelerators[END_REF]. These approaches are based on directives for specifying regions of code in Fortran or C programs that can be offloaded from a host CPU to an attached GPU by the compiler. None of these approaches, however, supports pipelining or other parallel patterns.

Conclusion and Future Work

We have presented high-level language annotations for C/C++ for developing pipelined applications on heterogeneous many-core architectures without having to deal with complex low-level architectural issues. We provided an overview of the associated implementation framework which is currently being developed within the European PEPPHER project. Our work relies on a component-based approach where pipeline stages correspond to multi-architectural components that encapsulate different implementation variants optimized by expert programmers for different execution units of a heterogeneous many-core system. A source-to-source compiler translates pipelined applications to an object-oriented coordination layer which is built on top of a heterogeneous task-based runtime system. The task-based runtime system attempts to schedule the best component implementation variants for parallel execution on the free execution units of a many-core system such that overall performance is optimized.

Our approach enables to run the same high-level application code without changes on homogeneous and heterogeneous multi-core architectures, delegating to the runtime system task scheduling and implementation variant selection. Experimental results on two different architectures are encouraging and indicate that a performance comparable to manual parallelization can be achieved, despite the considerably higher level of abstraction provided by our language features for the pipeline pattern.

For future work we plan to extend our framework with autotuning capabilities to, for example, determine replication counts and buffer sizes for pipeline stages. Furthermore, we plan to experiment with different runtime scheduling strategies as supported by StarPU and to provide support for other parallel patterns.

1 4 # 7 }

 47 # pragma pph pipeline with buffer ( FIFO ) 2 while ( data . size != 0) { 3 func1 ( iFile , data ) ; pragma pph stage buffer for port ( cdata , RANDOM ,8) Listing 1.2: Influencing Buffer Management.

  ... 1 pipe::BufferObject *blockBItem = bufferItemCreator(...); 2 pipe::Buffer *readOutBuf = pipe::createFIFOBuffer(blockBItem); 3 pipe::Stage *readStage = pipe::createStage(STAGE::SOURCE...); 4 pipe::Stage *compressStage = pipe::createStage(STAGE::INTER,…); ... 5 pipe::connectStage(read,0,compress,0,readOutBuf); 6 readStage->setInputBuffer(iFileIn,0); 7 compressStage->setReplication(N); 8 compressStage->setComputation(&compressComponent); 9 readStage->execute(); ...

(Fig. 1 :

 1 Fig. 1: Overview of the transformation process.

1 4 readBlock 7 # 9 }

 479 unsigned int N = g e t _ m a x _ c p u _ c o r e s () ; 2 # pragma pph pipeline with buffer ( FIFO , N *2) 3 while ( b != 0) { pragma pph stage buffer for port ( write .b , PRIORITY ) 8 w r i t e C o m p r e s s e d B l o c k ( file , b ) ; Listing 1.3: BZIP2 Compression Pipeline

1 5 # 8 } 9 wListing 1 . 4 :

 58914 unsigned int N = g e t _ m a x _ e x e c u t i o n _ u n i t s () ; 2 # pragma pph pipeline with buffer ( PRIORITY , N *2) 3 while ( image . number < 32) { 4 readImage ( file , image ) ; pragma pph stage replicate ( N ) { 6 r e s i z e A n d C o l o r C o n v e r t ( image ) ; 7 detectFace ( image , outImage ) ; r i t e F a c e D e t e c t e d I m a g e ( file , outImage ) ; 10 } OpenCV Image Processing Pipeline

  The Stage class encapsulates information

	... while(block.last != 1) { read(ifile,block); compress(block); write(ofile,block); } ...	Annotate	#pragma pipeline buffer[FIFO,2*N] while(block.last != 1) { read(ifile,block); #pragma stage replicate(N) compress(block); #pragma stage buffer_... write(ofile,block); }
						Analyze
	read	B	compress	B	write

Table 1 :

 1 bzip2 Performance Results (execution times in s)

			Architecture A			Architecture B
	# Cores	1	2	4	8	16	1	2	4	8
	TBB	248.26 135.63 66.72 32.12 14.44 245.52 122.01 62.75 33.19
	pbzip2	250.31 130.01 65.80 32.94 19.38 248.81 131.33 65.72 36.96
	PEPPHER 245.40 141.68 75.62 35.42 16.83 238.47 109.87 61.97 32.83

Table 2 :

 2 OpenCV Performance Results (execution times in secs)

	Architecture A
	Image Size	VGA SVGA XGA QXGA
	TBB (1 Core)	15.61 23.51 41.84 170.58
	PEPPHER (1 Core)	12.40 17.85 30.72 140.86
	Intel TBB (16 Core)	1.26 1.92 3.39 13.60
	PEPPHER (16 Cores)	1.16 1.72 2.91 12.33
	Architecture B
	TBB (1 Core)	12.75 20.07 35.15 145.68
	PEPPHER (1 Core)	9.62 14.33 24.94 111.45
	PEPPHER (1 Core + 1 GPU) 3.94 5.91 10.35 46.30
	PEPPHER (1 Core + 2 GPUs) 2.95 2.72 6.53 30.81
	TBB (8 Cores)	1.47 2.29 4.13 17.4
	PEPPHER (8 Cores)	1.18 1.78 3.58 13.69
	PEPPHER (7 Cores + 1 GPU) 1.13 1.63 2.91 11.89
	PEPPHER (6 Cores + 2 GPUs) 0.94 1.40 2.44 10.71

These functions must be pure, i.e. they must not access global data, they must be stateless, and they are to be executed non-preemptively.

Acknowledgment This work was supported by the European Commission as part of the FP7 Project PEPPHER under grant 248481.


François Goasdoué

Ioana Manolescu
email: ioana.manolescu@inria.fr

Alexandra Roatiş
email: alexandra.roatis@inria.fr

Getting More RDF Support from Relational Databases

Keywords: H.2.4 [Database Mgmt]: Systems-query processing Algorithms, Experimentation, Theory RDF fragments, RDF query reformulation, RDF saturation

We introduce the database fragment of RDF, which extends the popular Description Logic fragment, in particular with support for incomplete information. We then provide novel sound and complete saturation-and reformulation-based techniques for answering the Basic Graph Pattern queries of SPARQL in this fragment. Notably, we extend the state of the art on pushing RDF query processing within robust / efficient relational database management systems. Finally, we experimentally compare our query answering techniques using well-established datasets.

INTRODUCTION AND CONCEPTS

The Resource Description Framework (RDF) is a graphbased data model and the W3C standard for Semantic Web applications. An RDF graph is a set of triples of the form s p o . stating class and property assertions (Figure 2). RDF Schema (RDFS) allows enhancing RDF graphs by stating semantic constraints between classes and properties (Figure 2). Interestingly, RDF graphs can model incomplete information using blank nodes (labelled nulls), allowing to handle unknown classes, properties, and values.

RDF entailment is the mechanism through which, based on explicit triples and entailment rules, implicit RDF triples are derived. This allows defining the (finite) saturation of an RDF graph G, denoted G ∞ , obtained by making all the implicit triples explicit. From the RDF standard perspective, an RDF graph is semantically equivalent to its saturation.

We consider a subset of the SPARQL language, consisting of (unions of) conjunctive queries, defined by basic graph patterns (BGPs), i.e., sets of triple atoms.

A conjunctive query is denoted q(x):-t1, . . . , tα (x is empty in boolean queries). The variables x in the head of the query are called distinguished variables, and are a subset of the variables occurring in t1, . . . , tα. Evaluation treats the blank nodes in a query as non-distinguished variables. The (complete) answer set of a query q against G is obtained by the evaluation of q against G ∞ , denoted by q(G ∞ ).

In this paper we define the database (DB) fragment of RDF, strictly more expressive than the Description Logic fragment, that captures essential RDF features, such as incomplete information, and treats class and property names like any other value in the database. Then, we study query answering in this DB fragment, through the saturation-and reformulation-based approaches, for the BGP queries.

The positioning of our work w.r.t. the literature is sketched in Figure 1. More details are available at [3].

THE DATABASE FRAGMENT OF RDF

We define the database (DB) fragment of RDF by: • restricting RDF entailment to the entailment rules dedicated to RDF Schemas (Figure 3); • not restricting RDF graphs in any way. An RDF graph belonging to our DB fragment is an RDF database db = S, D , where the schema-level S and instancelevel D are disjoint sets of triples, respectively made of the RDFS statements and the RDF statements in db.

The saturation of a database db with this restricted rule set is denoted db ∝ . The evaluation of a query q against db is the normative evaluation of q against the RDF graph db, i.e., q(db), and the answer set of q against db is q(db ∝ ). the queries, to deal with entailed triples; after which query answering is reduced to query evaluation. We focus on answering instance-level queries, i.e., the usual database queries. Saturation-based query answering. Given a database db, Saturate(db) [3] is an algorithm that exhaustively applies 4 saturation rules on db plus all the gradually generated triples. The worst-case size (number of triples) of its output is in O(#db 2 ), where #db is the size of db. Saturate+(db) [3] is a multiset variant of Saturate(db) -a triple appears as many times as it can be entailed -allowing saturation maintenance upon updates, to avoid recomputing the whole saturation upon every update on db.

QUERY ANSWERING IN RDF

Theorem 1. For a query q and a database db, q(db ∝ ) = q(Saturate(db)) = q(set(Saturate+(db))) holds. Reformulation-based query answering. Given a query q and a database db, Reformulate(q, db) [3] is an algorithm that reformulates q, using 13 reformulation rules, into a set of queries, such that the union of the non-standard evaluations (see below) of these queries on db produces q(db ∝ ). The worst-case size (number of queries) of the output of Reformulate(q, db) is in O((6 * #db 2 ) #q ), with #db and #q the sizes (number of triples) of db and q respectively. Standard evaluation is based on assignments of all the query's variables and blank nodes into database values, treating blank nodes as non-distinguished variables. In contrast, when our Reformulate(q, db) algorithm brings blank nodes in queries, it refers precisely to these particular blank nodes in db. We therefore define the non-standard evaluation of a query q against a database db, denoted q(db), that only assigns the query variables, treating blank nodes as constants.

Theorem 2. For a database db and a query q against db, q(db ∝ ) = qσ ∈Reformulate(q,db) qσ(db) holds.

EXPERIMENTAL EVALUATION

We implemented our algorithms in Java 1.6 and delegate query evaluation to a PostgreSQL server v8.5. The instancelevel, set-and multiset-based saturation are stored in separate tables, identically indexed with 15 indexes for efficient query evaluation opportunities. The schema-level is kept in memory. All measured times are averaged over five runs.

We present results obtained for the DBpedia [8] dataset (#S = 5666 triples, #D = 27 million triples), other results are available at [3]. Saturation added 10% to the database size in tsat = 2, 742s and tsat+ = 2, 977s, where tsat, tsat+ is the saturation time using Saturate, resp. Saturate+.

For query answering, we hand-picked 20 queries of 1 to 4 atoms. We call the saturation threshold of a query q, or st(q), the integer n representing the minimum number of times one needs to run q for the whole saturation cost to amortize. Similarly, we define st + /st -for amortizing the maintenance overhead due to one triple insertion/deletion. Figure 4 shows that the thresholds are strongly correlated with the size of the reformulated query (in parentheses on the x axis). The larger the reformulated query, the lower the threshold: saturation pays off faster when reformulation is expensive. st is always higher than st + and st -, since st runs offset the complete saturation cost, whereas st + and st -need to offset the cost of maintaining saturation for just one triple added or deleted. Finally, st -is lower than st + : saturation costs particularly penalize frequent deletions.

Q 0 1 (9 7 9 3 ) Q 0 2 (8 1 8 8 ) Q 0 3 (2 2 2 0 ) Q 0 4 (4 6 3 ) Q 0 5 (3 4 7 ) Q 0 6 (3 9 ) Q 0 7 (1 1 ) Q 0 8 (1 ) Q 0 9 (9 7 9 3 ) Q 1 0 (2 2 2 9 ) Q 1 1 (4 6 3 ) Q 1 2 (3 4 7 ) Q 1 3 (3 9 ) Q 1 4 (1 ) Q 1 5 (9 7 9 3 ) Q 1 6 (4 6 3 ) Q 1 7 (3 9 ) Q 1 8 (1 ) Q 1 9 (4 6

Conclusion.

The saturation thresholds in RDF databases strongly depend on the size of the reformulated query (which depends on the schema), and the query selectivity. While saturation is the default choice in many RDF data management systems, for queries with small reformulations, its overhead is very high. This confirms the practical interest of our reformulation-based query answering technique.

CONCLUSION

Our work extends the state of the art on practical RDF data management based on RDBMS. Notably, we provide reformulation-and saturation-based query answering techniques that are robust to updates, and empirical performance thresholds between them. Further optimizations and performance comparisons are ongoing.

Figure 3 :

 3 Figure 3: Schema-and instance-level entailment.

Figure 2 :

 2 Figure 2: RDF & RDFS Statements (left). RDF graph G (right).

Figure 4 :

 4 Figure 4: Saturation threshold for DBpedia queries.

  Copyright is held by the author/owner(s).

		query language
		expressive power
	atomic / BGP queries	[6, 7]/[4]	this work
	relational
	conjunctive queries	[1, 2, 5]	RDF fragment expressive power
		DL	DB
	Figure 1: Positioning of our work.
	Triples			Entailed triple
	s rdfs:subClassOf o .,	o rdfs:subClassOf o1 .	s rdfs:subClassOf o1 .
	s rdfs:subPropertyOf o ., o rdfs:subPropertyOf o1 . s rdfs:subPropertyOf o1 .
	s rdfs:domain o .,	o rdfs:subClassOf o1 .	s rdfs:domain o1 .
	s rdfs:range o .,	o rdfs:subClassOf o1 .	s rdfs:range o1 .
	s rdfs:domain o .,	s1 rdfs:subPropertyOf s . s1 rdfs:domain o .
	s rdfs:range o .,	s1 rdfs:subPropertyOf s . s1 rdfs:range o .
	s1 rdfs:subClassOf s2 .,	s rdf:type s1 .		s rdf:type s2 .
	p1 rdfs:subPropertyOf p2 .,s p1 o .		s p2 o .
	p rdfs:domain s .,	s1 p o1 .		s1 rdf:type s .
	p rdfs:range s .,	s1 p o1 .		o1 rdf:type s .

  We investigate saturation-and reformulation-based query answering against RDF databases. Each technique performs a specific pre-processing step, either on the database or on Domain typing constraint s rdfs:domain o . Range typing constraint s rdfs:range o .

	RDF statements
	Class assertion	s rdf:type o .
	Property assertion	s p o .
	RDFS statements
	Subclass constraint	s rdfs:subClassOf o .
	Subproperty constraint	s rdfs:subPropertyOf o .

ACKNOWLEDGEMENTS

This research was partially supported by Digiteo through the DIM DW4RDF grant.