While most student code is assessed for correctness and functionality, recent work has looked at extending automatic assessment to include quality aspects. In software engineering code reviews help developers to increase the quality of a project by identifying and cleaning poor structures - commonly referred to as code smells. Despite the availability of professional tools, evaluating the quality of small programs at CS1 level is quite different from evaluating a complex software system. Thus, identifying meaningful quality criteria for small programs written by novices and either adapting current tools or designing new ones for that purpose are topics worth being investigated. The present work contributes to this aim by analysing the code produced by CS1 students from three different perspectives: (i) inspecting the feedback of automated tools - Hyperstyle and Pylint; (ii) matching the smells addressed by a set of refactoring rules; (iii) devising and using a manual rubric. A comparative analysis indeed highlights strengths and weaknesses of these approaches. Overall, automatic quality feedback needs to be complemented with classroom instruction to manually detect code issues and decide if they need refactoring. Additionally, such review activities have the potential to develop code comprehension by engaging novice programmers to reflect on their own code.

Testing and debugging studies at undergraduate level have focused on the needs of novice programmers. Novice struggles have been identified and activities have been developed to expose CS1 students to a range of bug types and debugging techniques. As computer science students gain coding experience and complete further programming courses, they are expected to become competent debuggers with limited or no further instruction. However, not all students advance at the same pace and more work is needed to understand the debugging skills of an average CS2 student. This study is focused on exploring the practices and habits developed by those intermediate students to validate this expectation and identify possible gaps that require more support. To become competent debuggers, students should test and debug their code locally before submission instead of relying on the assignment's testing script to report failed test cases. Thus, we designed an online quiz in order to capture student's testing and debugging habits before and after students submit their code to an automatic grading system. The quiz answers from a second-year elective programming subject indicates that the average student used at least 3 techniques for bug investigation, with 55% of students using diagnostic print statements (DPS), tracing of failed test cases, and reading code. Note that “reading code” to check the steps of computation was the only technique to be statistically significant in relation to course performance.

Whilst most undergraduate students eventually produce functionally correct code, they often disregard their code style and overall quality when it is not graded. As reported by the literature, quality defects affect both code structure and code style, and these issues seem to persist even in later years. This paper reports on the potential of a low-cost intervention that directed CS2 students to revise and refactor their code, with a specific focus on code structure, by resorting to a range of online refactoring resources.

Characterising code quality is a challenge that was addressed by Börstler et al. 's working group in 2017. As emerged from their study, educators, developers and students have different perceptions of the manifold aspects involved, and a major conclusion of that WG was that "code quality should be discussed more thoroughly in educational programs" [2, p. 70]. However, the lack of materials and the time constraints have slowed down progress in that regard.

Abstraction plays a key role in efficient problem solving: it helps to identify relationships and properties that support moving from basic brute force approaches towards simpler and more efficient solutions. The ability to abstract in problem solving is a difficult skill that should be nurtured by providing both examples and explicit guidance on how to use abstraction. In order to develop teaching materials we should first have a reasonable estimation of the students' current ability to abstract from the problem description as reflected in their solutions. In this study we have identified a simple problem, "EggCartons" which could be used as an exemplar to model abstraction in the classroom, due to its wide solution space. Its algorithmic solutions move up the ladder of abstraction, from brute force towards mathematical modelling. We visually inspected and classified the problem's solutions written by second year students, in order to explore students' current abstraction skills. The classification helped to identify four levels of abstraction that are relevant to other problems. The insights gained from this analysis provide a possible learning trajectory for abstraction in problem solving which could support undergraduate students to gradually increase the abstraction level of their algorithmic solutions.

Novice programmers naturally focus on writing code that is functionally correct over writing code that is readable and efficient. This emphasis on correctness over style is encouraged by the ubiquitous use of automated grading tools. Consequently, teaching students to write succinct, readable code that uses language-appropriate idioms is a challenge for educators. Prior work in computing education has catalogued the common code smells and anti-patterns often present in code produced by novices. However, there remains a need for good teaching resources and, importantly, evidence that these resources are both usable by students and produce the intended outcomes. In this paper, we propose a lab-based resource to help novices identify and refactor code smells when writing conditional statements. Our resource consists of four rules for simplifying conditionals that are derived from prior literature, and three accompanying practice tasks to which students can apply the rules. We describe our first experience using this resource in a large introductory programming course and explore (1) how well students use the provided rules to simplify correct but inelegant code, and (2) whether any effects persist on later code writing tasks. We found that students understood the rules and were able to apply them effectively to examples containing common code smells. We also found evidence that students continued to write more succinct code two weeks after using the resource. Finally, we make our resource available so that it can be adopted by other educators.

Every year, millions of students learn how to write programs. Learning activities for beginners almost always include programming tasks that require a student to write a program to solve a particular problem. When learning how to solve such a task, many students need feedback on their previous actions, and hints on how to proceed. In the case of programming, the feedback should take the steps a student has taken towards implementing a solution into account, and the hints should help a student to complete or improve a possibly partial solution. Only a limited number of learning environments for programming give feedback and hints on intermediate steps students take towards a solution, and little is known about the quality of the feedback provided. To determine the quality of feedback of such tools and to help further developing them, we create and curate data sets that show what kinds of steps students take when solving programming exercises for beginners, and what kind of feedback and hints should be provided. This working group aims to 1) select or create several data sets with steps students take to solve programming tasks, 2) introduce a method to annotate students' steps in these data sets, 3) attach feedback and hints to these steps, 4) set up a method to utilize these data sets in various learning environments for programming, and 5) analyse the quality of hints and feedback in these learning environments.

Research on novice programmers has focused heavily on identifying errors and misconceptions and helping novices to correct them. In contrast, there is a sparse but growing effort into helping students to evaluate and improve the quality of their code once it is functionally correct. One way to improve quality is to simplify code structure by getting rid of poorly written code patterns, or so called code smells. Although code smells for software developers are well catalogued, novices exhibit a different range of code smells compared to experts. A catalogue of novices' code smells and their transformations will help instructors to discuss code quality issues with their students. Smells related to conditional expressions and conditional statements have been reported both in novice and expert studies. Our poster focuses on lesser-known novice code smells related to iteration from the literature and it also introduces a new iterative pattern, named "AskFirstOrLast", and how to refactor it.

This Research Full Paper presents a study of programming strategies to manipulate data series presented in a range of CS1 courses. We collected and analyzed programs from multiple institutions in different countries, covering a range of programming languages (Python, Java, Go, and C). We started from a list of core strategies (that is, strategies that process the series as a whole, e.g., goals/plans for counting, linear search, etc.) drawn from the literature. We then expanded and refined the list, based on the analysis of the collected programs. We used a mixed method: we first analyzed the programs qualitatively to identify the recurring goals; then we conducted a quantitative analysis of the frequencies of goals. The result of the qualitative analysis is a data-driven list of basic goals that are required in order to cover the input, storage, and processing of data series, independently of the chosen programming language. The list has 13 well-separated goals (no goal in the list is a sub-goal of another one) that share a similar structure and the same level of abstraction. The quantitative analysis shows that the category of core goals is, not surprisingly, the most frequent one; around half of the programs contain a core goal, with total, count, and linear search being the most recurrent ones. Besides them, goals related to input and storage play a significant role as well: taken together, they occur with a frequency similar to that of core goals. The list of goals, if used to select or design practical exercises and teaching materials, can be a valid reference for CS1 instructors who want to foster the acquisition of strategic knowledge by their students. Implication for teaching and learning are discussed.

Learning transfer refers to the ability to correctly apply learned skills, knowledge and behaviors to new situations or contexts. This paper explores novice programmers' transfer through the analysis of two related coding tasks completed by CS1 students as part of their assessment. The first task was a take-home practical and the second task was a lab practical exam; both tasks requested the implementation of a C function with an integer parameter from which the digits are to be extracted and operated on. The solution set generated from each task by a cohort of 255 CS1 students has been explored and classified in order to determine the extent of transfer from the practice task to the later assessment task.

The Rainfall problem has been widely used to explore plan composition and programming errors by CS1 students. This work introduces the Inchworm problem, a conceptually straightforward task which must be solved using three interrelated skills: problem solving, algorithmic design and code implementation. The Inchworm is a holistic low stakes assessment of those three skills that provides insights on students' use of abstraction in problem solving while exposing the intricacies of code design. We tested this task with three cohorts of undergraduate students that have passed our core CS2 course. Most of them solved it in their first attempt, showing a reasonable mastery of basic algorithmic skills. In regards to problem solving strategies, most students chose to simulate the process described in the problem, step by step, with less than 10% choosing the more efficient mathematical approach. Their simulations used 4 different modelling strategies, all correct but with varying abstraction and efficiency levels. Simulation designs with poor performance indicate possible gaps in software development skills by disregarding the memory and computational cost of their solutions.

This poster examines learning to program from three different angles or colour-tinted glasses. These somehow overlapping angles are (1) learning a new language, using principles of second language acquisition, (2) mastering a skill, based on skill acquisition theory and (3) solving problems in a range of contexts, thus frequently requiring both near and far transfer of programming strategies.

A computer systems course using the "Nand2Tetris" materials has been taught in our institution for two years. Assignment work is based around extensions or variations of the projects provided. The challenge described in this paper was to develop a variation of project 5 that supported student's authentic learning of basic CPU design within time constrains and fitted with existing course materials. A 2-phase CPU design assignment was created that asked students to complete first the CPU design from the text book, and then complete an alternative CPU which replaced the D-register with a small register bank; each phase was weighted equally. The second phase reinforced the concepts learned in the first phase by making students identify the significant overlaps when decoding and generating control bits, as well as being exposed to hardware design choices at register level. Note files for project 5 can be easily sourced from MOOC resources, while this is not the case for the second phase as this was our own CPU design. Other alternative designs are possible, which can be used in rotation for this course. We could also ask students in advance CA courses to design and code their own extension of the Hack machine.

Novice programmers should develop program comprehension skills as they learn to code so that they are able both to read and reason about code created by others, and to reflect on their code when writing, debugging or extending it. This work takes a little-explored perspective on the comprehension of small programs by asking students to decide if two code segments are equivalent or not in terms of carrying out the same computation. A variation of Euclid's algorithm, that extends the greatest common divisor calculation to more than two numbers, was chosen for this work, as it has an adequate level of complexity and its semantics are not obvious. Four program transformations of the original code were developed: two transformations were equivalent and two were not. 73.5% of students were able to identify correctly the four options and 75.5% provided good insights on the equivalent program flow to justify their choices. The overall task has a SOLO mean of 3.19, which indicates code equivalence is a suitable and approachable task to analyse program execution at novice level. In addition, the data analysis suggests that students' code-reading abilities beyond basic tracing may be generally underestimated and we should investigate how to bridge the potential gap between reasoning about program execution and extracting its purpose.

This study explores novice programmers' abilities to design and code a string manipulation task in C after one semester of tertiary instruction. String manipulation is an important skill for novice programmers to master as most applications deal with text and/or interact with the user. The analysis shows most novice programmers (88%) were able to sketch their own programming plan to print a word in pyramid style. 53% of students chose to control the printing letter by letter (character level) and 32% updated and printed the word as a whole (string level). However only 6% used string functions, apart from strlen() and strcmp(), to implement their plan. This indicated a low level of transfer from their most recent class activity which focused on the C string library. As expected, not all succeeded to correctly implement their plan: 56% were correct at character level and 63% at string level, resulting in 49% of the whole cohort completing the task. Their code has been thoroughly analysed to identify implementation issues, and logical, syntax and plan errors are reported and discussed.

High Performance Computing (HPC) is the ability to process data and perform complex calculations at extremely high speeds. Current HPC platforms can achieve calculations on the order of quadrillions of calculations per second with quintillions on the horizon. The past three decades witnessed a vast increase in the use of HPC across different scientific, engineering and business communities, for example, sequencing the genome, predicting climate changes, designing modern aerodynamics, or establishing customer preferences. Although HPC has been well incorporated into science curricula such as bioinformatics, the same cannot be said for most computing programs. This working group will explore how HPC can make inroads into computer science education, from the undergraduate to postgraduate levels. The group will address research questions designed to investigate topics such as identifying and handling barriers that inhibit the adoption of HPC in educational environments, how to incorporate HPC into various curricula, and how HPC can be leveraged to enhance applied critical thinking and problem solving skills. Four deliverables include: (1) a catalog of core HPC educational concepts, (2) HPC curricula for contemporary computing needs, such as in artificial intelligence, cyberanalytics, data science and engineering, or internet of things, (3) possible infrastructures for implementing HPC coursework, and (4) HPC-related feedback to the CC2020 project.

This working group asserts that Program Comprehension (PC) plays a critical part in the writing process. For example, this abstract is written from a basic draft that we have edited and revised until it clearly presents our idea. Similarly, a program is written in an incremental manner, with each step being tested, debugged and extended until the program achieves its goal. Novice programmers should develop their program comprehension as they learn to code, so that they are able to read and reason about code while they are writing it. To foster such competencies our group has identified two main goals: (1) to collect and define learning activities that explicitly cover key components of program comprehension and (2) to define possible learning trajectories that will guide teachers using those learning activities in their CS0/CS1 or K-12 courses.

Students of introductory programming courses are expected to develop higher-order thinking skills to inspect, understand and modify code. However, although novices can correctly write small programs, they appear to lack a more abstract, comprehensive grasp of basic constructs, such as conceiving the overall effect of alternative conditional flows. This work takes a little-explored perspective on the comprehension of tiny programs by asking students to reason about reversing conditionals in either an imperative or a functional context. More specifically, besides deciding if the given constructs can be reversed, students had to justify their choice by writing a reversing program or by providing suitable counterexamples. The students' answers to four reversibility questions have been analysed through the lens of the SOLO taxonomy. 45% of students correctly identified the reversibility for the four code items; furthermore, more than 50% of each cohort were able to provide correct justifications for at least three of their four answers. Most incorrect answers were due to failures to consider border cases or to edit the conditional expressions appropriately to reverse the construct. Differences in comprehension between functional and imperative languages are explored indicating the explicit else paths of the functional examples facilitate comprehension compared with the implicit else (no update) of its imperative counterpart.

Iteration is one of the basic programming constructs taught in a CS1 course. Students learn to use loops by being exposed to a range of loop examples, initially with scalar values and then over composite data such as vectors. When writing a finite loop to iterate over a vector, we can iterate upwards or downwards. In many cases, the order does not change the outcome; however, for some tasks it is important to consider which direction is most suitable before writing a solution. For example, if we want to shift the elements of a vector one position to the right (left), we should choose a downward (upward) loop. However, when we asked undergraduate students to implement the shift right task, most of them used an upward loop. This outcome indicates the students didn't consider the loop direction before coding the iterative task. We hypothesise that this was in part due to course materials favouring upward loops. To confirm this hypothesis, we have analysed the examples presented in our local CS0/CS1 courses as well as four popular MOOCs. This analysis has corroborated an overwhelming bias towards upward loops. We have also found a lack of instruction regarding the possible impact of direction on code efficiency. Thus, in order to improve novice programmers' iteration skills, we propose CS1 examples that expose students to a more balanced mix of up/down loops and the explicit choice of direction.

Summary Low‐diameter networks require non‐minimal adaptive routing to deal with varying traffic characteristics and avoid pathological performance. Such routing is based on local estimations of network congestion, based on link‐level flow control credits. Dragonfly networks based on the extensions of commodity Ethernet networks using OpenFlow have been proposed for large HPC deployments with low power consumption. However, this network technology does not implement credit‐based flow control. This work explores a range of routing solutions based on exploiting explicit congestion notification messages (in particular, 802.1Qau) to adapt the number of packets using non‐minimal paths. The design (denoted QCN‐Switch) associates a probability value to each output port. This value is updated to reflect downstream congestion and used to statistically divert traffic away from congested areas when the load is uneven, as in the case of adversarial traffic. A feedback comparison variant is designed to separate the cases of uniform traffic at saturation and adversarial traffic at low loads. Evaluation results show that QCN‐Switch is a competitive design for both the uniform traffic and adversarial traffic. Furthermore, it is able to react to changes in traffic conditions in 0.4 ms or less. A sensitivity analysis identifies the best configuration and shows its performance trade‐offs.

This lighting talk provides a literature review that supports the concept that small failures can have a positive effect on learning compared with more traditional scaffolding techniques that prevent students from failing. From a sociocultural approach to education, scaffolding is provided through mediated dialogue within the students' zone of proximal development (ZDP) to minimize failure. However, productive failure has been found to promote wider exploration and to provide deeper learning experiences by assisting learners to self-identify knowledge gaps. Related to the idea of scaffolding in teaching, is the concept of task difficulty. Selecting problem-solving tasks that are neither too difficult nor too easy is critical in assisting learning as this reduces learner frustration and can foster development of learner self-efficacy. Many issues need to be addressed when exploring the ideal mediated task difficulty including: (1) how to assess learners' ZDP, (2) how to find an adequate balance between challenging tasks that seek to traverse learners' ZPD and the degree and type of failure they can trigger, and (3) how to provide support to learn from experienced failure. Our first goal, in collaboration with interdisciplinary multi-institutional partners, is to design sequenced activities that ask students to attempt a problem-solving task prior to any instruction/scaffolding activities usually provided to guide task completion. This will trigger foreseeable small failures, which can be used as learning opportunities. Note that this approach may not only foster learning, as observed at high school level, but also build resilience.

We want undergraduate students to develop higher-order thinking skills that enable them to master program behaviour. Nonetheless, many students of both introductory and advanced programming courses appear to struggle with the abstraction required for this purpose. In particular, a recent think-aloud study showed a group of students were able to reason about and reverse the effect of assignments and vector updates, but most of them failed when asked to reverse a seemingly simple conditional statement.

Even though a computer science or computing-oriented degree is unavoidably broken into semesters and courses, we always hope that our students form a holistic picture of the discipline by the time they graduate. Yet we do not have too many opportunities to make this point in a convincing manner. The goal of this working group will be to address a well-defined portion of this problem: revealing the significant connections between algorithmic courses (such as Discrete Math, Data Structures, Algorithms) and systems oriented courses (such as Organization, Computer Networks, Operating Systems, and Hardware) that may be missed by students.

Abstraction is a core skill for both programming and problem solving, however it is also a challenge for many students to develop a correct understanding of abstract concepts, such as program behaviour, which causes them to struggle with both introductory and advanced programming courses. Thus, evaluating students' ability to reason about programs should be an important topic for CS education.

There is a wealth of literature dealing with the difficulties of novice programmers with basic programming constructs such as variables, assignment and conditionals. In this paper we extend the study to two other core CS1 topics: loops and vectors (represented as single dimensional arrays). By the end of their first semester of instruction, students are expected to have acquired both the ability to reproduce given syntactic structure and basic design skills that allow them to write small pieces of code that extend, modify or combine in new ways the basic programming constructs.

Networks on Chip (NoCs) have a large impact on system performance, area and energy. Considering the characteristics of the memory subsystem while designing the NoC helps identify improvement opportunities and build more efficient designs. Leveraging the frequent request-reply pattern, our proposal dynamically builds the reply path in advance, is able to share circuits between messages, and even removes some implicit replies, significantly reducing NoC latency. A careful implementation of this circuit reservation mechanism achieves an average 17% reduction in router energy consumption, 8% smaller router area and a 2% system performance increase, compared with its baseline counterpart.

The performance of an interconnection network is typically measured by two metrics: average latency and peak network throughput. Average network throughput is usually reported in the belief the network is fair and all source nodes are supposedly able to inject at the same rate. However, most systems exhibit significant network unfairness under non-uniform loads. At high loads, if link utilization is uneven, the injection matrix will also become uneven. This unfairness significantly degrades the performance of some nodes, and eventually the whole system. Fairness issues have been previously reported for direct topologies such as mesh and torus, but this work evaluates throughput fairness in indirect networks, specifically the fat-tree topology. We will see fairness is still an issue for indirect networks in the presence of hot-spots. The SAT protocol was initially proposed to provide throughput fairness for ring networks. This paper extends the original protocol to implement a fairness injection mechanism that works for indirect networks. A thorough evaluation will show that for most scenarios it is possible to achieve throughput fairness without a significant lost of peak throughput.

Direct networks suffer significant network unfairness under non-uniform heavy loads; nodes near high traffic areas are hardly able to inject new packets while nodes at low traffic areas may inject packets at high rates. The reported average throughput does not reflect the large differences in node throughput amongst the network. Age-based arbitration has been proposed to achieve latency fairness and in doing so it will indirectly improve throughput fairness as well. However, as throughput fairness is only an issue at heavy loads, we would like a less intrusive method that can be applied to a range of network designs without limiting their routing or arbitration policies. This paper presents a simple injection fairness protocol that guarantees all nodes can inject at a similar rate at high loads regardless of their location. Tests with a variety of non-uniform loads will prove the success of the protocol for a range of network sizes.

Any simulation-based evaluation of an interconnection network proposal requires a good characterization of the workload. Synthetic traffic patterns based on independent traffic sources are commonly used to measure performance in terms of average latency and peak throughput. As they do not capture the level of self-throttling that occurs in most parallel applications, they can produce inaccurate throughput estimates at high loads. Thus, workloads that resemble the varying levels of synchronization of actual applications are needed to study the performance of interconnection networks. One approach is to use simple, burst-synchronized synthetic workloads that emulate the self-throttling of many parallel applications. To validate this approach, we compare the gains achieved by a restrictive injection mechanism under this workload with those obtained using traces from the NAS Parallel Benchmarks. This study confirms that the burst-synchronized traffic model provides reasonable performance estimates, which could be improved by taking into account dependency chains between messages.

Recent parallel systems use multiple injection ports and various injection policies, but little is known about their impact on network performance. This paper evaluates the influence that these injection interfaces have on maximum sustained throughput in adaptive cut-through torus networks by modeling the number of injection queues (1 or 4), and the allocation of new packets to those queues. Network evaluations for medium to large size 2D tori show that designs with multiple injection ports do not improve performance under uniform traffic. On the contrary, they result in more pressure from the injection interface to acquire the scarce network resources of an already clogged system. Interestingly, for small networks, a single injection FIFO queue, with the HOLE it entails, indirectly provides the much needed injection control. For networks with thousands of nodes and multiple injection channels, as those being implemented in current massively parallel processors, this implicit form of congestion control is not enough. In such systems, restrictive injection policies are required to prevent routers from being flooded with new packets for loads beyond saturation.

This work presents the design and evaluation of an adaptive packet router aimed at supporting CC-NUMA traffic. We exploit a simple and efficient packet injection mechanism to avoid deadlock, which leads to a fully, adaptive routing by employing only three virtual channels. In addition, we selectively use output buffers for implementing the most utilized virtual paths in order to reduce head-of-line blocking. The careful implementation of these features has resulted in a good trade-off between the network performance and hardware cost. The outcome of this research is a high-performance adaptive router (HPAR), which adequately balances the needs of parallel applications: minimal network latency at low loads and high throughput at heavy loads. The paper includes an evaluation process in which HPAR is compared with other adaptive routers using FIFO input bufferring, with or without additional virtual channels to reduce head-of-line blocking. This evaluation contemplates both the VLSI costs of each router and their performance under synthetic and real application workloads. To make the comparison fair, all the routers use the same efficient deadlock avoidance mechanism. In all the experiments, HPAR exhibited the best response among all the routers tested. Moreover, the observed packet latencies were comparable to those exhibited by simpler routers. Therefore, HPAR can be considered as a suitable candidate to implement packet interchange in next generations of CC-NUMA multiprocessors.

The Midimew network is an excellent contender for implementing the communication subsystem of a high performance computer. This network is an optimal 2D topology in the sense there are no other symmetric direct networks of degree 4 with a lower average distance or diameter. In fact, it reduces the diameter of the well known torus network by approximately □2. Although the topology was proposed and analyzed a decade ago, the lack of simple deadlock avoidance mechanisms prevented its utilization up to date. This study solved this drawback by applying the Bubble switching mechanism, a low cost deadlock-avoidance strategy developed by the authors. Moreover, by using routing tables we can configure our Virtual Cut-Through adaptive router to implement either a torus or a Midimew network. Thus, we can exploit the topological advantages of Midimew networks by simply changing the disposition of the wrap-around connections of its torus counterpart, without increasing the network implementation cost. To prove this assertion, we have carried out a thorough evaluation, from the hardware cost of the router to the parallel system performance under real loads.

A router design for torus networks that significantly reduces message latency over traditional wormhole routers is presented in this paper. This new router implements virtual cut-through switching and fully-adaptive minimal routing. Packet deadlock is avoided by providing escape ways governed by Bubble flow control, a mechanism that guarantees enough free buffer space in the network to allow continuous packet movement. Both deterministic and adaptive Bubble routers have been designed in VLSI using VHDL synthesis tools. Adopting a fair quantitative comparison, we demonstrate that Bubble routers exhibit a reduction in base latency values over 40% with respect to the corresponding wormhole routers, without any penalty in network throughput. With much lower VLSI costs than adaptive wormhole routers, the adaptive Bubble router is even faster than deterministic wormhole routers based on virtual channels.

Supercomputer performance is highly dependent on its interconnection subsystem design.In this paper we study how different architectural approaches for router design impact into system performance when running real parallel applications.A thorough methodology has been employed to quantify this impact.Architectural router decisions have been chosen taking into account the constraints of the underlying VLSI technology.After that, an exhaustive evaluation of the interconnection network under standard synthetic traffic has been carried out.Finally, an execution-driven simulation environment has been used to assess the consequences of several router designs on the performance of the entire machine.We will show that low-level decisions, as the adequate selection of router's arbiter, significantly reduce the execution time of parallel applications.To illustrate the effects of the router architecture on system performance two benchmarks were selected: Radix and MPSD. IntroductionIn the field of high-performance computing, distributed shared-memory multiprocessors (DSMS) are becoming widespread.These parallel computers implement a single address space, either with coherent caches (SGI Origin 2000 [13]) or without them (Cray T3E 1181).The communication time involved on fetching remote data is one of the main overheads which limits the performance of many parallel applications.Moreover, cc-NUMA machines impose additional overheads due to synchronization amongst processes and coherence maintenance.As processor computing power increases, communication performance should increase accordingly in order to adequately balance the system.

Communications in a multicomputer system consist of heterogeneous traffic in which messages exhibit a variety of sizes.Network response is highly dependent on message length distribution, as reported in most network evaluation studies.Hence, router design should be optimized for dealing with heterogeneous traffic.This study analyzes the interaction amongst short and long messages in networks with bimodal length traffic: both single packet traffic (20 flits) and multipacket messages (200 flits).Router design determines the access of both traffic classes to the network resources so we have considered multiple alternatives, from the generic CT or WH static router to variations of the segment router proposed in [9], which maps the two traffic classes into two separate virtual networks.Having independent injection queues for each virtual network and adjusting the channel multiplexing policy to favour short or long messages provides good performance and added flexibility when compared to its cut-through counterpart.

This paper presents results concerning the design and testing of a fast network chip (the MPI) for parallel computers. We briefly introduce the theoretical results on which the MPI chip design was based and describe its architecture. The chip has been fabricated and tested in small prototype system. Based on parameters measured using this prototype and a simulator implemented at the logic level we have been able to accurately model the performance of larger networks based on this chip under a variety of synthetic loads. Extensive results are presented based on these simulations