Abstract Reading and understanding existing code is a crucial part of software engineering. We focus on the understanding of Boolean expressions, which control the flow of the execution. Such expressions can often be written in different ways that are logically equivalent, but there has been no systematic research on the possible advantages of one formulation over another. Our goal is to examine the effect of various factors on understanding such expressions, leading to guidelines for selecting the most understandable version from a set of logically equivalent expressions. To achieve this goal, we conducted a controlled experiment using all 16 simple Boolean expressions with two variables, a connecting operator, and possible negations. We define and empirically compare two distinct levels of understanding these expressions: tracing , which involves following the program’s execution for a specific input, and comprehension , which encompasses a generalization of how the code behaves for all possible inputs. The experiment involved 362 participants, 57% of which had more than 6 years of programming experience. The results reveal that comprehension not only takes longer but also leads to a higher error rate compared to tracing. Furthermore, expressions involving the logical operator were found to be more challenging on average than those with , but this difficulty manifested only at the comprehension level. One of the sources of this difference appears to be an interaction between the logical operators and , and we discuss possible models which may explain this effect. The observed differences in understanding equivalent expressions highlight the importance of selecting which expression to use. Our findings suggest that Boolean expressions with and fewer negations tend to improve code readability, making them preferable for writing understandable code. But these recommendations need to be verified in the general context of Boolean expressions, including those that are more complex than the ones we considered.

Context: Motivation is known to improve performance. In software development, in particular, there has been considerable interest in the motivation of contributors to open-source. Objective: We would like to predict motivation, in various settings. We identify 11 motivators from the literature (enjoying programming, ownership of code, learning, self-use, etc.), and evaluate their relative effect on motivation using supervised learning. Method: We conducted a survey with 66 questions on motivation which was completed by 521 developers. Most of the questions used an 11-point scale. We also conducted a follow-up survey, enabling investigation of motivation improvement given improvement in motivators. Results: Predictive analysis—investigating how diverse motivators influence the probability of high motivation—provided valuable insights. The correlations between the different motivators are low, implying their independence. High values in all 11 motivators predict an increased probability of high motivation. In addition, improvement analysis shows that an increase in most motivators predicts an increase in general motivation. Conclusions: All 11 motivators indeed support motivation, but only moderately. No single motivator suffices to predict high motivation or motivation improvement, and each motivator sheds light on a different aspect of motivation. Models based on multiple motivators predict motivation improvement with up to 94% accuracy, better than any single motivator. Editor’s note: Open Science material was validated by the Journal of Systems and Software Open Science Board .

Motivation is an important factor in software development. However, it is a subjective concept that is hard to quantify and study empirically. In order to use the wealth of data available about real software development projects in GitHub, we represent the motivation of developers using labeling functions. These are validated heuristics that need only be better than a guess, computable on a dataset. We define four labeling functions for motivation based on behavioral cues like working in diverse hours of the day. We validated the functions by agreement with respect to a developers survey, per person behavior, and temporal changes. We then apply them to 150 thousand developers working on GitHub projects. Using the identification of motivated developers, we measure developer performance gaps. We show that motivated developers have up to 70% longer activity period, produce up to 300% more commits, and invest up to 44% more time per commit.

The flow of control in computer programs is shaped by conditional branches. The Boolean expressions which determine the outcome of a branch may have an effect on the readability of the code. In particular, negations can make such expressions harder to understand. We conduct an experiment with 205 professional developers who needed to understand different logical expressions. The results show that the time needed to understand different expressions of similar size can vary significantly. In general, expressions with more negations take more time, and double negations are especially troublesome. However, there are multiple other factors that also have an effect. For example, literals which are TRUE take less time to process than literals that are FALSE. Regularity (where either all variables have negations or all do not, or where either all literals are TRUE or all are FALSE) also helps. But there are many confounding interactions between the factors, leading to complex outcomes. For example, when comparing De Morgan’s logically-equivalent pairs of expressions, we found that understanding a negated OR took slightly more time than the AND of two negations, but there was no difference between a negated AND and the OR of two negations. The factors we identified as influencing the understanding of expressions may contribute to advancing our knowledge of cognitive processes involved in understanding logical expressions, but much additional work is still needed. At the same time, the comparisons of equivalent forms provide some practical advice on how to write more understandable expressions.

Recursion has the reputation of being hard to teach and understand. Our goal is to identify precisely what it is about recursion that makes it hard, and use this to devise a systematic teaching plan. We first make a distinction between regular recursion and tail recursion --- the special case where the recursive call is the last command that is executed by the function. Tail recursion is the preferred form used in functional programming, because it simplifies memory management, and we hypothesize that it is also easier to understand. We conducted a controlled experiment with 139 participants, in which they were asked to understand different recursive functions. This revealed that tail recursion, when it is natural to use, is indeed easier to understand than the more general form of recursion where significant processing is performed after the recursive call. But it also showed that using tail recursion may come with a price, as when achieving the tail form requires a transformation of the code that obfuscates the underlying recursive algorithm. We conclude that having significant processing after the recursive call, or distorting the code so as to remove such processing, are major factors that make recursion hard. We therefore suggest to start teaching recursion with a basic form of tail recursion, and then progress to more complicated cases with processing after the recursive call. Transformations to tail form should be taught last, if at all.

It is generally accepted that variables with a narrow syntactic scope can have short names, whereas variables with a broad scope require more informative longer names. We study how names are given in practice, using a dataset of nearly 640 thousand variable names from Java methods, recently introduced by Aman et al. We extend their original analysis by using a finer division of scopes into ranges. We find that indeed variables with broader scope tend to be slightly longer and to include more words. There is also a progression of changes in name structures, with fewer single-letter names and more compound names as the scope increases. But the biggest differences occur at the low-scope end, not the high-scope end. In addition, we present more evidence that words of 6 letters or more are often abbreviated, but this is not affected by scope. Finally, we also analyze the distribution of popularity of names and of words in names, and show that single letter names are much more varied and common than usually thought, even when the variables have a broad scope.

Eye tracking studies have shown that reading code, in contradistinction to reading text, includes many vertical jumps. As different lines of code may have quite different functions (e.g., variable definition, flow control, or computation), it is important to accurately identify the lines being read. We design experiments that require a specific line of text to be scrutinized. Using the distribution of gazes around this line, we then calculate how the precision with which we can identify the line being read depends on the font size and spacing. The results indicate that, even after correcting for systematic bias, unnaturally large fonts and spacing may be required for reliable line identification. Interestingly, during the experiments, the participants also repeatedly re-checked their task and if they were looking at the correct line, leading to vertical jumps similar to those observed when reading code. This suggests that observed reading patterns may be “inefficient,” in the sense that participants feel the need to repeat actions beyond the minimal number apparently required for the task. This may have implications regarding the interpretation of reading patterns. In particular, reading does not reflect only the extraction of information from the text or code. Rather, reading patterns may also reflect other types of activities, such as getting a general orientation, and searching for specific locations in the context of performing a particular task.

Most of the text in a computer program is composed of the names of variables and functions. These names are selected by one developer, and need to be understood by others. This is similar to the role of words written in natural language. But there are several marked differences between the names in a program and the words in a book. First, names are frequently composed of multiple existing words, in an attempt to capture nuanced meanings and intents. Second, because of the use of multiple words, names can be rather long. Third, conventions may also allow names to be very short, and many single-letter names are used. But despite these differences, the general statistics of names are rather similar to the statistics of words. Like words, the distribution of names is close to a Zipf distribution. Also, popular names tend to be shorter than rarely used names. However, the underlying vocabulary if different. The composition of words leads to a more diverse vocabulary that can grow without bounds. But if we look at the individual words used in compound names, we find a rather limited vocabulary. These properties help explain the predictability of software, and how it can coincide with the large variability of names. It also suggests that it may be beneficial to model programs at the level of individual words rather than at the level of source code tokens.

Memorable function and variable names are useful for developers: they reduce the need to re-check how objects are named when one wants to use them, and they enhance comprehension when encountered when reading code. We look at the possible interplay between the information contained in names and how memorable they are. We show in two independent experiments involving a total of 190 subjects that informative names are usually easier to recollect than similar-length names which contain less focused information. Interestingly, we find that less-experienced and female participants are better at remembering the less informative names. We also find that short names, which are not just abbreviated but actually contain less information, are significantly more memorable. Hence a good choice would be to use the the shortest name that includes the most focused and pertinent information.

The names of variables and functions serve as implicit documentation and are instrumental for program comprehension. But choosing good meaningful names is hard. We perform a sequence of experiments in which a total of 334 subjects are required to choose names in given programming scenarios. The first experiment shows that the probability that two developers would select the same name is low: in the 47 instances in our experiments the median probability was only 6.9 percent. At the same time, given that a specific name is chosen, it is usually understood by the majority of developers. Analysis of the names given in the experiment suggests a model where naming is a (not necessarily cognizant or serial) three-step process: (1) selecting the concepts to include in the name, (2) choosing the words to represent each concept, and (3) constructing a name using these words. A followup experiment, using the same experimental setup, then checked whether using this model explicitly can improve the quality of names. The results were that names selected by subjects using the model were judged by two independent judges to be superior to names chosen in the original experiment by a ratio of two-to-one. Using the model appears to encourage the use of more concepts and longer names.

Intermediate variables can be used to break complex expressions into more manageable smaller expressions, which may be easier to understand. But it is unclear when and whether this actually helps. We conducted an experiment in which subjects read 6 mathematical functions and were supposed to give them meaningful names. 113 subjects participated, of which 58% had 3 or more years of programming work experience. Each function had 3 versions: using a compound expression, using intermediate variables with meaningless names, or using intermediate variables with meaningful names. The results were that in only one case there was a significant difference between the two extreme versions, in favor of the one with intermediate variables with meaningful names. This case was the function that was the hardest to understand to begin with. In two additional cases using intermediate variables with meaningless names appears to have caused a slight decrease in understanding. In all other cases the code structure did not make much of a difference. As it is hard to anticipate what others will find difficult to understand, the conclusion is that using intermediate variables is generally desirable. However, this recommendation hinges on giving them good names.

Understanding program code is a complicated endeavor. As such, myriad different factors can influence the outcome. Investigations of program comprehension, and in particular those using controlled experiments, have to take these factors into account. In order to promote the development and use of sound experimental methodology, we discuss potential problems with regard to the experimental subjects, the code they work on, the tasks they are asked to perform, and the metrics for their performance.

Variable and function names are extremely important for program comprehension. It is therefore also important to study how developers select names. But controlled experiments on naming are hindered by the need to describe to experimental subjects what it is they need to name. Words appearing in these descriptions may then find their way into the names, leading to a bias in the results. We suggest that this problem can be alleviated by using emojis or other small graphics in lieu of key words in the descriptions. A replication of previous work on naming, this time including such emojis and graphics, indeed led to a more diverse and less biased choice of words in the names than when using English descriptions.

Program comprehension accounts for a large portion of software development costs and effort. The academic literature contains research on program comprehension of short code snippets, but comprehension at the system level is no less important. We claim that comprehending a software system is a distinct activity that differs from code comprehension. We interview experienced developers, architects, and managers in the software industry and open-source community, to uncover the meaning of program comprehension at the system level. The interviews demonstrate, among other things, that system comprehension is detached from code and programming language, and includes scope that is not captured in the code. It focuses on the structure of the system and less on the code itself. This is a continuous, iterative process, which mixes white-box and black-box approaches at different layers of the system, and combines both bottom-up and top-down comprehension strategies.

Program comprehension concerns the ability to understand code written by others. But not all code is the same. We use an experimental platform fashioned as an online game-like environment to measure how quickly and accurately 222 professional programmers can interpret code snippets with similar functionality but different structures. The results indicate, inter alia, that 'for' loops are significantly harder than 'if's, that some but not all negations make a predicate harder, and that loops counting down are slightly harder than loops counting up. This demonstrates how the effect of syntactic structures, different ways to express predicates, and the use of known idioms can be measured empirically, and that syntactic structures are not necessarily the most important factor. By amassing many more empirical results like these it may be possible to derive better code complexity metrics than we have today.

It is widely accepted that meaningful variable names are important for comprehension. We conducted a controlled experiment in which 9 professional developers try to understand 6 methods from production util classes, either with the original variable names or with names replaced by meaningless single letters. Results show that parameter names are more significant for comprehension than local variables. But, surprisingly, we also found that in 3 of the methods there were no significant differences between the control and experimental groups, due to poor and even misleading variable names. These disturbingly common bad names reflect the subjective nature of naming, and highlight the need for additional research on how variable names are interpreted and how better names can be chosen.

It is widely accepted that variable names in computer programs should be meaningful, and that this aids program comprehension. "Meaningful" is commonly interpreted as favoring long descriptive names. However, there is at least some use of short and even single-letter names: using 'i' in loops is very common, and we show (by extracting variable names from 1000 popular github projects in 5 languages) that some other letters are also widely used. In addition, controlled experiments with different versions of the same functions (specifically, different variable names) failed to show significant differences in ability to modify the code. Finally, an online survey showed that certain letters are strongly associated with certain types and meanings. This implies that a single letter can in fact convey meaning. The conclusion from all this is that single letter variables can indeed be used beneficially in certain cases, leading to more concise code.

Analysts are interested in two categories of performance metrics: those concerned with time (response or wait time), and those concerned with rates (throughput or utilization, which reflect productivity and how well resources are used). In principle, these two categories are independent of each other, and both should be evaluated. But a common mistake is to "measure" the throughput in open-system evaluations, where the throughput is actually dictated directly by the workload. In order to evaluate throughput, the system model must include a feedback loop which modulates the workload being processed. The common solution is to create a pure closed system with a fixed number of users, who submit jobs in a loop. However, such behavior is often unrealistic. We review and analyze two alternative models that provide the required feedback by combining open and closed components: the mixed model which includes two such job classes, and the re-open model in which open user arrivals are combined with performance-dependent closed repetition of jobs by these users. These models allow evaluations of the trade-off between response time and throughput, including the throughput as it is observed by each user.

New scheduling algorithms are first evaluated in simulations. In simulations, the workload has a huge influence on the measured performance of the simulated system. Simulation workloads typically assume an open system model and the workload is unaffected by the system's performance. As a result, the throughput is fixed and only the wait times and slowdown are evaluated. Therefore instead of evaluating the users' productivity, they evaluate the users' convenience.

New scheduling algorithms are first evaluated using simulation. In these simulations, the workload has a huge influence on the measured performance of the simulated system. Therefore, it is customary to use workload traces recorded previously from real systems. Such open-system simulations preserve all the jobs' properties. However, preserving the jobs' arrival times actually destroys the logic of the user's workflow, especially dependencies and think times between successive jobs. Furthermore, performance in such simulations is measured by the average wait time and slowdown, under the fixed load and throughput conditions dictated by the trace. Therefore, it is impossible to evaluate the system's effect on throughput and productivity. As an alternative we propose semi-open trace based simulations that include dynamic user activity and internal feedback from the system to the users. In these simulations, like in a real system, users adjust their job-submittal behavior in response to system performance. As a result, the simulations produce different loads and throughputs for different scheduling algorithms or parametrizations. We implemented such a simulation for evaluating the schedulers of parallel job systems. We also developed a novel user-aware scheduler designed specifically to increase users' productivity. While conventional simulations cannot measure this scheduler's influence reliably, and would suggest it is useless, our simulation evaluates it realistically and shows its beneficial effect on the users' productivity and the system's throughput.

Code obfuscation techniques are widely used in industry to increase protection of source code and intellectual property. The idea is that even if attackers gain hold of source code, it will be hard for them to understand what it does and how. Thus obfuscation techniques are specifically targeted at human comprehension of code. We suggest that the ideas and experience embedded in obfuscations can be used to learn about comprehension. In particular, we survey known obfuscation techniques and use them in an attempt to derive metrics for code (in) comprehensibility. This leads to emphasis on issues such as identifier naming, which are typically left on the sidelines in discussions of code comprehension, and motivates increased efforts to measure their effect.

Regular code, which includes repetitions of the same basic pattern, has been shown to have an effect on code comprehension: a regular function can be just as easy to comprehend as an irregular one with the same functionality, despite being longer and including more control constructs. It has been speculated that this effect is due to leveraging the understanding of the first instances to ease the understanding of repeated instances of the pattern. To verify and quantify this effect, we use eye tracking to measure the time and effort spent reading and understanding regular code. The results are that time and effort invested in the initial code segments are indeed much larger than those spent on the later ones, and the decay in effort can be modeled by an exponential or cubic model. This shows that syntactic code complexity metrics (such as LOC and MCC) need to be made context-sensitive, e.g. By giving reduced weight to repeated segments according to their place in the sequence.

It is naturally easier to comprehend simple code relative to complicated code. Regrettably, there is little agreement on how to effectively measure code complexity. As a result simple generalpurpose metrics are often used, such as lines of code (LOC), Mc- Cabe’s cyclomatic complexity (MCC), and Halstead’s metrics. But such metrics just count syntactic features, and ignore details of the code’s global structure, which may also have an effect on understandability. In particular, we suggest that code regularity—where the same structures are repeated time after time—may significantly reduce complexity, because once one figures out the basic repeated element it is easier to understand additional instances. We demonstrate this by controlled experiments where subjects perform cognitive tasks on different versions of the same basic function. The results indicate that versions with significant regularity lead to better comprehension, while taking similar time, despite being longer and having higherMCC. These results indicate that regularity is another attribute of code that should be taken into account in the context of studying the code’s complexity and comprehension. Moreover, the fact that regularity may compensate for LOC and MCC demonstrates that complexity cannot be decomposed into independently addable contributions by individual attributes.

Program comprehension is a vital mental process in any maintenance activity. It becomes decisive as functions get larger. Such functions are burdened with very many programming constructs as lines of code (LOC) strongly correlate with the McCabe’s cyclomatic complexity (MCC). This makes it hard to capture the whole code of such functions and as a result hinders grasping their structural properties that might be essential for maintenance. Program visualization is known as a key solution that assists in comprehending complex systems. As a matter of fact we have shown, in a recent work, that control structure diagrams (CSD) could be useful to better understand and discover structural properties of such functions. For example, we found that the code regularity property, and even cloning, can be easily identified by CSDs. This paper presents JCSD, which is an Eclipse plug-in that implements CSD diagrams for Java methods. In particular it visualizes the control structure and nesting of a Java method, and by this it easily conveys structural characteristics of the code to the programmer and helps him to better understand and refactor.

Evaluating the performance of a computer system requires the use of representative workloads. Therefore it is customary to use recorded job traces in simulations to evaluate the performance of proposed parallel job schedulers. We argue that this practice retains unimportant attributes of the workload, at the expense of other more important attributes. Specifically, using traces in open-system simulations retains the exact timestamps at which jobs are submitted. But in a real system these times depend on how users react to the performance of previous jobs, and it is more important to preserve the logical structure of dependencies between jobs than the specific timestamps. Using dependency information extracted from traces, we show how a simulation can preserve these dependencies. To do so we also extract user behavior, in terms of sessions and think times between the termination of one batch of jobs and the submission of a subsequent batch.

SUMMARY Evaluating the performance of a computer system is based on using representative workloads. Common practice is to either use real workload traces to drive simulations or use statistical workload models that are based on such traces. Such models allow various workload attributes to be manipulated, thus providing desirable flexibility, but may lose details of the workload's internal structure. To overcome this, we suggest to combine the benefits of real traces and flexible modeling. Focusing on the problem of evaluating the performance of parallel job schedulers, we partition the trace of submitted jobs into independent subtraces representing different users and then recombine them in various ways, while maintaining features such as long‐range dependence and the daily and weekly cycles of activity. This facilitates the creation of longer workload traces that enable longer simulations, the creation of multiple statistically similar workloads that can be used to gauge confidence intervals, the creation of workloads with different load levels, and increasing the frequency of specific events like large surges of activity. Copyright © 2014 John Wiley & Sons, Ltd.

The Linux kernel is configured for specific uses by manipulations of the source code during the compilation process. These manipulations are performed by the C pre-processor (CPP), based on in-line directives. Such directives, and the interleaving of multiple versions of the code that they allow, may cause difficulties in code comprehension. To better understand the effects of CPP, we perform a deep analysis of the configurability of the Linux kernel. We found significant inconsistencies between the source code and the configuration control system. Focusing on the thousands of config options appearing in the source code, we found that their distribution is heavy-tailed, with some options having more than a thousand instances in the code. Such wide use seems to imply a massive coupling between different parts of the system. However, we argue that employing a purely syntactic analysis is insufficient. By involving semantic considerations, we find that in reality the coupling induced by the very frequent options is limited. Moreover, even at the syntactic level the adverse effects of CPP are limited, as there is little nesting and the expressions controlling conditional compilation are usually very simple. But it could be even better if the configuration system undergoes a clean up. On the other hand, we found that the code controlled by CPP is very heterogeneous and may exhibit intimate mingling with non-variable code. As a result the applicability of alternative mechanisms such as aspects is hard to envision.

Evaluating the performance of a computer system is based on using representative workloads. Common practice is to either use real workload traces to drive simulations, or else to use statistical workload models that are based on such traces. Such models allow various workload attributes to be manipulated, thus providing desirable flexibility, but may lose details of the workload's internal structure. To overcome this, we suggest to combine the benefits of real traces and flexible modeling. Focusing on the problem of evaluating the performance of parallel job schedulers, we partition each trace into independent subtraces representing different users, and then re-combine them in various ways, while maintaining features like the daily and weekly cycles of activity. This facilitates the creation of longer workload traces that enable longer simulations, the creation of multiple statistically similar workloads that can be used to gauge confidence intervals, and the creation of workloads with different load levels.

System bottlenecks, namely those resources which are subjected to high contention, constrain system performance. Hence effective resource management should be done by focusing on the bottleneck resources and allocating them to the most deserving clients. It has been shown that for any combination of entitlements and requests a fair allocation of bottleneck resources can be found, using an off-line algorithm that is given full information in advance regarding the needs of each client. We extend this result to the on-line case with no prior information. To this end we introduce a simple greedy algorithm. In essence, when a scheduling decision needs to be made, this algorithm selects the client that has the largest minimal gap between its entitlement and its current allocation among all the bottleneck resources. Importantly, this algorithm takes a global view of the system, and assigns each client a single priority based on his usage of all the resources; this single priority is then used to make coordinated scheduling decisions on all the resources. Extensive simulations show that this algorithm achieves fair allocations according to the desired entitlements for a wide range of conditions, without using any prior information regarding resource requirements. It also follows shifting usage patterns, including situations where the bottlenecks change with time.

Fair allocation has been studied intensively in both economics and computer science. This subject has aroused renewed interest with the advent of virtualization and cloud computing. Prior work has typically focused on mechanisms for fair sharing of a single resource. We consider a variant where each user is entitled to a certain fraction of the system's resources, and has a fixed usage profile describing how much he would want from each resource. We provide a new definition for the simultaneous fair allocation of multiple continuously-divisible resources that we call bottleneck-based fairness (BBF). Roughly speaking, an allocation of resources is considered fair if every user either gets all the resources he wishes for, or else gets at least his entitlement on some bottleneck resource, and therefore cannot complain about not receiving more. We show that BBF has several desirable properties such as providing an incentive for sharing, and also promotes high overall utilization of resources; we also compare BBF carefully to another notion of fairness proposed recently, dominant resource fairness.

McCabe's Cyclomatic Complexity (MCC) is a widely used metric for the complexity of control flow. Common usage decrees that functions should not have an MCC above 50, and preferably much less. However, the Linux kernel includes more than 800 functions with MCC values above 50, and over the years 369 functions have had an MCC of 100 or more. Moreover, some of these functions undergo extensive evolution, indicating that developers are successful in coping with the supposed high complexity. We attempt to explain this by analyzing the structure of such functions and showing that in many cases they are in fact well-structured. At the same time, we observe cases where developers indeed refactor the code in order to reduce complexity. These observations indicate that a high MCC is not necessarily an impediment to code comprehension, and support the notion that complexity cannot be fully captured using simple syntactic code metrics.

Activity logs from large-scale systems facilitate the study of user behavior, which can be used to improve and tune the user experience. However, the available data often lacks important elements such as the identification of user sessions. Previous work typically compensated for this by setting a threshold of around 30 minutes, and assuming that breaks in activity longer than the threshold reflect breaks between sessions. We show that using such a global threshold introduces artifacts that may affect the analysis, because there is a high probability that long sessions are not identified correctly. As an alternative, we suggest that a suitable individual threshold be found for each user, based on that user's activity pattern. Applying this approach to a large dataset from the AOL search engine leads to a distribution of session durations that is free of artifacts like those that appear when using a global threshold.

Locality is often characterized by working sets, defined by Denning as the set of distinct addresses referenced within a certain window of time. This definition ignores the fact that dramatic differences exist between the usage patterns of frequently used data and transient data. We therefore propose to extend Denning's definition with that of core working sets, which identify blocks that are used most frequently and for the longest time. The concept of a core motivates the design of dual-cache structures that provide special treatment for the core. In particular, we present a probabilistic locality predictor for L1 caches that leverages the skewed popularity of blocks to distinguish transient cache insertions from more persistent ones. We further present a dual L1 design that inserts only frequently used blocks into a low-latency, low-power, direct-mapped main cache, while serving others from a small fully associative filter. To reduce the prohibitive cost of such a filter, we present a content addressable memory design that eliminates most of the costly lookups using a small auxiliary lookup table. The proposed design enables a 16K direct-mapped L1 cache, augmented with a small 2K filter, to outperform a 32K 4-way cache, while at the same time consumes 70-80 percent less dynamic power and 40 percent less static power.

A basic problem in managing web servers is capacity planning. A partial solution is to use content adaptation, where the system automatically trades off quality for throughput, e.g. by eliminating graphical decorations and adjusting page layout. We evaluate this approach based on a full implementation in Apache and increasing load patterns. The implementation uses two alternative versions of the files, and employs URL rewriting rules to select which version to use. Triggering a switch from one version to the other is done based on readily available load metrics. The experiments show that throughput can be increased by a factor of 2 to 4 at the price of minor to acceptable deterioration in graphical quality. Increasing throughput by an order of magnitude is also possible, but requires larger compromises. Nevertheless, this is still achievable without a real effect on content. Thus content adaptation is a viable tool, but may be insufficient by itself for handling huge surges in load such as flash crowds.

Virtual machine monitors, especially when used for server consolidation, need to enforce a predefined sharing of resources among the running virtual machines. We propose a new mechanism for doing so that provides improved pacing in the face of heterogeneous allocations and priorities. This mechanism lends from token-bucket metering and from virtual-time scheduling, and prioritizes the different clients based on the divergence between their desired allocations and the actual consumptions. The ideas are demonstrated by implementations for the CPU and networking subsystems of the Linux kernel. Notably, both use exactly the same basic module; future plans include using it for disk I/O as well.

A basic problem in the management of web servers is capacity planning: you want enough capacity to be able to serve peak loads, but not too much so as to avoid excessive costs. It is therefore important to know the load that web service places on the CPU, disk, and network. We analyze these loads for representative web sites, and find that with normal caching the disk is not expected to be a bottleneck, and that reducing the number of requests made is more important than reducing the total size. We then consider the option of trading off quality for throughput, as may be necessary to handle flash crowds. The suggested approaches include the elimination of graphical decorations and previews, the compression of large images, the consolidation of style sheets and JavaScript code in the main HTML page, and the removal of unimportant blocks from the design.

A premier goal of resource allocators in virtualization environments is to control the relative resource consumption of the different virtual machines, and moreover, to be able to change the relative allocations at will. However, it is not clear what it means to provide a certain fraction of the machine when multiple resources are involved. We suggest that a promising interpretation is to identify the system bottleneck at each instant, and to enforce the desired allocation on that device. This in turn induces an efficient allocation of the other devices.

Computer workloads have many attributes. When modeling these workloads it is often difficult to decide which attributes are important, and which can be abstracted away. In many cases, the modeler only includes attributes that are believed to be important, and ignores the rest. We argue, however, that this can lead to impaired workloads and unreliable system evaluations. Using parallel job scheduling as a case study, and daily cycles of activity as the attribute in dispute, we present two schedulers whose simulated performance seems identical without cycles, but then becomes significantly different when daily cycles are included in the workload. We trace this to the ability of one scheduler to prioritize interactive jobs, which leads to implicitly delaying less critical work to nighttime, when it can utilize resources that otherwise would have been left idle. Notably, this was not a design feature of this scheduler, but rather an emergent property that was not anticipated in advance.

It is customary to use open-system trace-driven simulations to evaluate the performance of parallel-system schedulers. As a consequence, all schedulers have evolved to optimize the packing of jobs in the schedule, as a means to improve a number of performance metrics that are conjectured to be correlated with user satisfaction, with the premise that this will result in a higher productivity in reality. We argue that these simulations suffer from severe limitations that lead to suboptimal scheduler designs and to even dismissing potentially good design alternatives. We propose an alternative simulation methodology called site-level simulation, in which the workload for the evaluation is generated dynamically by user models that interact with the system. We present a novel scheduler called CREASY that exploits knowledge on user behavior to directly improve user satisfaction and compare its performance to the original packing-based EASY scheduler. We show that user productivity improves by up to 50 percent under the user-aware design, while according to the conventional metrics, performance may actually degrade.

Collecting and analyzing data lies at the basis of the scientific method: findings about nature usher new ideas, and experimental results support or refute theories. All this is not very prevalent in computer science, possibly due to the fact that computer systems are man made, and not perceived as a natural phenomenon. But computer systems and their interactions with their users are actually complex enough to require objective observations and measurements. We'll survey several examples related to parallel and other systems, in which we attempt to further our understanding of architectural choices, system evaluation, and user behavior. In all the cases, the emphasis is not on heroic data collection efforts, but rather on afresh look at existing data, and uncovering surprising, interesting, and useful information. Using such empirical information is necessary in order to ensure that systems and evaluations are relevant to the real world.

Understanding the detailed behavior of an operating system is crucial for making informed design decisions. But such an understanding is very hard to achieve, due to the increasing complexity of such systems and the fact that they are implemented and maintained by large and diverse groups of developers. Tools like KLogger --- presented in this paper --- can help by enabling fine-grained logging of system events and the sharing of a logging infrastructure between multiple developers and researchers, facilitating a methodology where design evaluation can be an integral part of kernel development. We demonstrate the need for such methodology by a host of case studies, using KLogger to better understand various subsystems in the Linux kernel, and pinpointing overheads and problems therein.

Observing the workload on a computer system during a short (but not too short) time interval may lead to distributions that are significantly different from those that would be observed over much longer intervals. Rather than describing such phenomena using involved non-stationary models, we propose a simple global distribution coupled with a localized sampling process. We quantify the effect by the maximal deviation between the global distribution and the distribution as observed over a limited slice of time, and find that in real workload data from parallel supercomputers this deviation is significantly larger than would be observed at random. Likewise, we find that the workloads at different sites also differ from each other. These findings motivate the development of adaptive systems, which adjust their parameters as they learn about their workloads, and also the development of parametrized workload models that exhibit such locality of sampling, which are required in order to evaluate adaptive systems.

Intuitively, it seems that understanding how the performance of a system affects its users requires research in psychology and the conducting of live experiments. We demonstrate that it is possible to uncover the effect from traces of the system. In particular, we found that the behavior of users of parallel systems is correlated with the response time of their jobs, not the slowdown as was previously assumed. We show that response times affect the decision of users to continue or abort their interactive session with the system, and that this may relate to expectations the users develop. Although this research was conducted in the context of parallel systems, we believe our results are more general and may pertain to other types of systems as well.

Simulations sometimes lead to observed sensitivity to configuration parameters as well as inconsistent performance results. The question is then what is the true effect and what is a coincidental artifact of the evaluation. The shaking methodology answers this by executing multiple simulations under small perturbations to the input workload, and calculating the average performance result; if the effect persists we can be more confident that it is real, whereas if it disappears it was an artifact. We present several examples where the sensitivity that appears in results based on a single evaluation is eliminated or considerably reduced by the shaking methodology. While our examples come from evaluations of scheduling algorithms for supercomputers, we believe the method has wider applicability.

The most commonly used scheduling algorithm for parallel supercomputers is FCFS with backfilling, as originally introduced in the EASY scheduler. Backfilling means that short jobs are allowed to run ahead of their time provided they do not delay previously queued jobs (or at least the first queued job). However, predictions have not been incorporated into production schedulers, partially due to a misconception (that we resolve) claiming inaccuracy actually improves performance, but mainly because underprediction is technically unacceptable: users will not tolerate jobs being killed just because system predictions were too short. We solve this problem by divorcing kill-time from the runtime prediction and correcting predictions adaptively as needed if they are proved wrong. The end result is a surprisingly simple scheduler, which requires minimal deviations from current practices (e.g., using FCFS as the basis) and behaves exactly like EASY as far as users are concerned; nevertheless, it achieves significant improvements in performance, predictability, and accuracy. Notably, this is based on a very simple runtime predictor that just averages the runtimes of the last two jobs by the same user; counter intuitively, our results indicate that using recent data is more important than mining the history for similar jobs. All the techniques suggested in this paper can be used to enhance any backfilling algorithm and are not limited to EASY

The performance of computer systems depends, among other things, on the workload. This motivates the use of real workloads (as recorded in activity logs) to drive simulations of new designs. Unfortunately, real workloads may contain various anomalies that contaminate the data. A previously unrecognized type of anomaly is workload flurries: rare surges of activity with a repetitive nature, caused by a single user, that dominate the workload for a relatively short period. We find that long workloads often include at least one such event. We show that in the context of parallel job scheduling these events can have a significant effect on performance evaluation results, e.g. a very small perturbation of the simulation conditions might lead to a large and disproportional change in the outcome. This instability is due to jobs in the flurry being effected in unison, a consequence of the flurry's repetitive nature. We therefore advocate that flurries be filtered out before the workload is used, in order to achieve stable and more reliable evaluation results (analogously to the removal of outliers in statistical analysis). At the same time, we note that more research is needed on the possible effects of flurries

The performance of computer systems depends, among other things, on the workload. Performance evaluations are therefore often done using logs of workloads on current productions systems, under the assumption that such real workloads are representative and reliable; likewise, workload modeling is typically based on real workloads. We show, however, that real workloads may also contain anomalies that make them non-representative and unreliable. This is a special case of multi-class workloads, where one class is the "real" workload which we wish to use in the evaluation, and the other class contaminates the log with "bogus" data. We provide several examples of this situation, including a previously unrecognized type of anomaly we call "workload flurries": surges of activity with a repetitive nature, caused by a single user, that dominate the workload for a relatively short period. Using a workload with such anomalies in effect emphasizes rare and unique events (e.g. occurring for a few days out of two years of logged data), and risks optimizing the design decision for the anomalous workload at the expense of the normal workload. Thus we claim that such anomalies should be removed from the workload before it is used in evaluations, and that ignoring them is actually an unjustifiable approach.

Mass-count disparity is the technical underpinning of the "mice and elephants" phenomenon - that most samples are small, but a few are huge - which may be the most important attribute of heavy-tailed distributions. We propose to visualize this phenomenon by plotting the conventional distribution and the mass distribution together in the same plot. This then leads to a natural quantification of the effect based on the distance between the two distributions. Such a quantification addresses this important phenomenon directly, taking the full distribution into account, rather than focusing on the mathematical properties of the tail of the distribution. In particular, it shows that the Pareto distribution with tail index 1 \le a \le 2 actually has a relatively low mass-count disparity; the effects often observed are the result of combining some other distribution with a Pareto tail.

The conventional performance evaluation methodology for parallel system schedulers uses an open model to generate the workloads used in simulations. In many cases recorded workload traces are simply played back, assuming that they are reliable representatives of real workloads, and leading to the expectation that the simulation results actually predict the scheduler’s true performance. We show that the lack of feedback in these workloads results in performance prediction errors, which may reach hundreds of percents. We also show that load scaling, as currently performed, further ruins the representativeness of the workload, by generating conditions which cannot exist in a real environment. As an alternative, we suggest a novel sitelevel modeling evaluation methodology, in which we model not only the actions of the scheduler but also the activity of users who generate the workload dynamically. This advances the simulation in a manner that reliably mimics feedback effects found in real sites. In particular, saturation is avoided because the generation of additional work is throttled when the system is overloaded. While our experiments were conducted in the context of parallel scheduling, the idea of site-level simulation is applicable to many other types of systems.

Desktop operating systems such as Windows and Linux base scheduling decisions on CPU consumption; processes that consume fewer CPU cycles are prioritized, assuming that interactive processes gain from this since they spend most of their time waiting for user input. However, this doesn't work for modern multimedia applications which require significant CPU resources. We therefore suggest a new metric to identify interactive processes by explicitly measuring interactions with the user, and we use it to design and implement a process scheduler. Measurements using a variety of applications indicate that this scheduler is very effective in distinguishing between competing interactive and noninteractive processes.

As parallel jobs get bigger in size and finer in granularity, "system noise" is increasingly becoming a problem. In fact, fine-grained jobs on clusters with thousands of SMP nodes run faster if a processor is intentionally left idle (per node), thus enabling a separation of "system noise" from the computation. Paying a cost in average processing speed at a node for the sake of eliminating occasional processes delays is (unfortunately) beneficial, as such delays are enormously magnified when one late process holds up thousands of peers with which it synchronizes.We provide a probabilistic argument showing that, under certain conditions, the effect of such noise is linearly proportional to the size of the cluster (as is often empirically observed). We then identify a major source of noise to be indirect overhead of periodic OS clock interrupts ("ticks"), that are used by all general-purpose OSs as a means of maintaining control. This is shown for various grain sizes, platforms, tick frequencies, and OSs. To eliminate such noise, we suggest replacing ticks with an alternative mechanism we call "smart timers". This turns out to also be in line with needs of desktop and mobile computing, increasing the chances of the suggested change to be accepted.

The complexity of modern computer systems may enable minor variations in performance evaluation procedures to actually determine the outcome. Our case study concerns the comparison of two parallel job schedulers, using different workloads and metrics. It shows that metrics may be sensitive to different job classes, and not measure the performance of the whole workload in an impartial manner. Workload models may implicitly assume that some workload attribute is unimportant and does not warrant modeling; this too can turn out to be wrong. As such effects are hard to predict, a careful experimental methodology is needed in order to find and verify them.

Many scientific and high-performance computing applications consist of multiple processes running on different processors that communicate frequently. Because of their synchronization needs, these applications can suffer severe performance penalties if their processes are not all coscheduled to run together. Two common approaches to coscheduling jobs are batch scheduling, wherein nodes are dedicated for the duration of the run, and gang scheduling, wherein time slicing is coordinated across processors. Both work well when jobs are load-balanced and make use of the entire parallel machine. However, these conditions are rarely met and most realistic workloads consequently suffer from both internal and external fragmentation, in which resources and processors are left idle because jobs cannot be packed with perfect efficiency. This situation leads to reduced utilization and suboptimal performance. Flexible coscheduling (FCS) addresses this problem by monitoring each job's computation granularity and communication pattern and scheduling jobs based on their synchronization and load-balancing requirements. In particular, jobs that do not require stringent synchronization are identified, and are not coscheduled; instead, these processes are used to reduce fragmentation. FCS has been fully implemented on top of the STORM resource manager on a 256-processor alpha cluster and compared to batch, gang, and implicit coscheduling algorithms. This paper describes in detail the implementation of FCS and its performance evaluation with a variety of workloads, including large-scale benchmarks, scientific applications, and dynamic workloads. The experimental results show that FCS saturates at higher loads than other algorithms (up to 54 percent higher in some cases), and displays lower response times and slowdown than the other algorithms in nearly all scenarios.

Current desktop operating systems use CPU utilization (or lack thereof) to prioritize processes for scheduling. This was thought to be beneficial for interactive processes, under the assumption that they spend much of their time waiting for user input. This reasoning fails for modern multimedia applications. For example, playing a movie in parallel with a heavy background job usually leads to poor graphical results, as these jobs are indistinguishable in terms of CPU usage. Suggested solutions involve shifting the burden to the user or programmer, which we claim is unsatisfactory; instead, we seek an automatic solution. Our attempts using new metrics based on CPU usage failed. We therefore propose and implement a novel scheme of identifying interactive and multimedia applications by directly quantifying the I/O between an application and the user (keyboard, mouse, and screen activity). Preliminary results indicate that prioritizing processes according to this metric indeed solves the aforementioned problem, demonstrating that operating systems can indeed provide better support for multimedia and interactive applications. Additionally, once user I/O data is available, it opens intriguing new possibilities to system designers.

It is commonly agreed that scheduling mechanisms in general purpose operating systems do not provide adequate support for modern interactive applications, notably multimedia applications. The common solution to this problem is to devise specialized scheduling mechanisms that take the speci c needs of such applications into account. A much simpler alternative is to better tune existing systems. In particular, we show that conventional scheduling algorithms typically only have little and possibly misleading information regarding the CPU usage of processes, because increasing CPU rates have caused the common 100 Hz clock interrupt rate to be coarser than most application time quanta. We therefore conduct an experimental analysis of what happens if this rate is signi cantly increased. Results indicate that much higher clock interrupt rates are possible with acceptable overheads, and lead to much better information. In addition we show that increasing the clock rate can provide a measure of support for soft real-time requirements, even when using a general-purpose operating system. For example, we achieve a sub-millisecond latency under heavily loaded conditions.

Conventional gang scheduling has the disadvantage that when processes perform I/O or blocking communication, their processors remain idle because alternative processes cannot be run independently of their own gangs. To alleviate this problem, we suggest a slight relaxation of this rule: match gangs that make heavy use of the CPU with gangs that make light use of the CPU (presumably due to I/O or communication activity), and schedule such pairs together, allowing the local scheduler on each node to select either of the two processes at any instant. As I/O-intensive gangs make light use of the CPU, this only causes a minor degradation in the service to compute-bound jobs. This degradation is more than offset by the overall improvement in system performance due to the better utilization of the resources.

One of the scarce resources that limits communication performance is buffer space on the network interface card. This becomes even worse when it is partitioned among several time-sliced processes. However, if gang scheduling is used, it is possible to swap buffer contents as part of the context switch, giving each job the full buffer space for the duration of its quantum. This does not suffer undue overhead, as the buffer space is mainly used to allow a larger flow-control window, and typically does not contain many packets that need to be stored.

Abstract Clusters use commodity hardware and software components to provide an environment for high‐performance parallel processing. A major issue in the development of a cluster system is the choice of the operating system that will run on each node. We compare three alternatives: Windows NT, Linux, and QNX—a real‐time microkernel. The comparison is based on expressive power, performance, and ease‐of‐use metrics. The result is that none of these systems has a clear advantage over the others in all the metrics, but that each has its strong and weak points. Thus any choice of a base system will involve some technical compromises, but not major ones. Copyright © 2001 John Wiley & Sons, Ltd.

Scheduling jobs on the IBM SP2 system and many other distributed-memory MPPs is usually done by giving each job a partition of the machine for its exclusive use. Allocating such partitions in the order in which the jobs arrive (FCFS scheduling) is fair and predictable, but suffers from severe fragmentation, leading to low utilization. This situation led to the development of the EASY scheduler which uses aggressive backfilling: Small jobs are moved ahead to fill in holes in the schedule, provided they do not delay the first job in the queue. We compare this approach with a more conservative approach in which small jobs move ahead only if they do not delay any job in the queue and show that the relative performance of the two schemes depends on the workload. For workloads typical on SP2 systems, the aggressive approach is indeed better, but, for other workloads, both algorithms are similar. In addition, we study the sensitivity of backfilling to the accuracy of the runtime estimates provided by the users and find a very surprising result. Backfilling actually works better when users overestimate the runtime by a substantial factor.

A major problem with time slicing on parallel machines is memory pressure, as the resulting paging activity damages the synchronism among a job's processes. An alternative is to impose admission controls, and only admit jobs that fit into the available memory. Despite suffering from delayed execution, this leads to better overall performance by preventing the harmful effects of paging and thrashing.

This paper proposes a technique that enables performing multi-cycle (multiplication, division, square-root …) computations in a single cycle. The technique is based on the notion of memoing: saving the input and output of previous calculations and using the output if the input is encountered again. This technique is especially suitable for Multi-Media (MM) processing. In MM applications the local entropy of the data tends to be low which results in repeated operations on the same datum.The inputs and outputs of assembly level operations are stored in cache-like lookup tables and accessed in parallel to the conventional computation. A successful lookup gives the result of a multi-cycle computation in a single cycle, and a failed lookup doesn't necessitate a penalty in computation time.Results of simulations have shown that on the average, for a modestly sized memo-table, about 40% of the floating point multiplications and 50% of the floating point divisions, in Multi-Media applications, can be avoided by using the values within the memo-table, leading to an average computational speedup of more than 20%.

ParC is an extension of the C programming language with block-oriented parallel constructs that allow the programmer to express fine-grain parallelism in a shared-memory model. It is suitable for the expression of parallel shared-memory algorithms, and also conducive for the parallelization of sequential C programs. In addition, performance enhancing transformations can be applied within the language, without resorting to low-level programming. The language includes closed constructs to create parallelism, as well as instructions to cause the termination of parallel activities and to enforce synchronization. The parallel constructs are used to define the scope of shared variables, and also to delimit the sets of activities that are influenced by termination or synchronization instructions. The semantics of parallelism are discussed, especially relating to the discrepancy between the limited number of physical processors and the potentially much larger number of parallel activities in a program.

The Vesta parallel file system is designed to provide parallel file access to application programs running on multicomputers with parallel I/O subsystems. Vesta uses a new abstraction of files: a file is not a sequence of bytes, but rather it can be partitioned into multiple disjoint sequences that are accessed in parallel. The partitioning—which can also be changed dynamically—reduces the need for synchronization and coordination during the access. Some control over the layout of data is also provided, so the layout can be matched with the anticipated access patterns. The system is fully implemented and forms the basis for the AIX Parallel I/O File System on the IBM SP2. The implementation does not compromise scalability or parallelism. In fact, all data accesses are done directly to the I/O node that contains the requested data, without any indirection or access to shared metadata. Disk mapping and caching functions are confined to each I/O node, so there is no need to keep data coherent across nodes. Performance measurements shown good scalability with increased resources. Moreover, different access patterns are show to achieve similar performance.

The Vesta parallel file system is intended to solve the I/O problems of massively parallel multicomputers executing numerically intensive scientific applications. It provides parallel access from the applications to files distributed across multiple storage nodes in the multicomputer, thereby exposing an opportunity for high-bandwidth data transfer across the multicomputer's low-latency network. The Vesta interface provides a user-defined parallel view of file data, which gives users some control over the layout of data. This is useful for tailoring data layout to much common access patterns. The interface also allows user-defined partitioning and repartitioning of files without moving data among storage nodes. Libraries with higher-level interfaces that hide the layout details, while exploiting the power of parallel access, may be implemented above the basic interface. It is shown how collective I/O operations can be implemented, and six parallel access modes to Vesta files are defined. Each mode has unique characteristics in terms of how the processes share the file and how their accesses are interleaved. The combination of user-defined file partitioning and the six access modes gives users very versatile parallel file access.

Abstract We present an on-line (run-time) algorithm that manages the granularity of parallel functional programs. The algorithm exploits useful parallelism when it exists, and ignores ineffective parallelism in programs that produce many small tasks. The idea is to balance the amount of local work with the cost of distributing the work. This is achieved by ensuring that for every parallel task spawned, an amount of work that equals the cost of the spawn is performed locally. We analyse several cases and compare the algorithm to the optimal execution. In most cases the algorithm competes well with the optimal algorithm, even though the optimal algorithm has information about the future evolution of the computation that is not available to the on-line algorithm. This is quite remarkable considering we have chosen extreme cases that have contradicting optimal executions. Moreover, we show that no other on-line algorithm can be consistently better than it. We also present experimental results that demonstrate the effectiveness of the algorithm.