13948740
Scalarization Using Loop Alignment and Loop Skewing
Array syntax, which is supported in many technical programming languages, adds expressive power by allowing operations on and assignments to whole arrays and array sections. To compile an array assignment statement to a uniprocessor, the language processor must convert the statement into a loop that has the same meaning. This process is called scalarization.Scalarization presents a significant technical problem because an array assignment needs to be implemented as if all inputs are fetched before any outputs are stored. Since a loop intermixes loads and stores, the compiler typically allocates a temporary array to hold the intermediate result. Because these extra temporary arrays can cause performance problems in cache, many techniques have been developed to avoid their use or minimize their size.In this paper, we present a novel application of two compiler strategies—loop alignment and loop skewing—to address this problem. We show that these strategies can achieve the asymptotically minimal memory allocation for stencil computations. Our experiments with loop alignment and loop skewing demonstrate that it is extremely effective in improving memory hierarchy performance of Fortran 90 array code on standard uniprocessors. The result should be applicable to other array languages, such as MATLAB.
1449662
A tool for teaching curve design
This paper describes a tool for teaching curve design. This tool is a component of the software tools to be used in a computing with geometry course [3, 4] that is being developed under the support of National Science Foundation. Curve design is important in computer graphics, animation, and computer aided design. Unfortunately, curve design requires very involved mathematics even though many curve design concepts are intuitive. As a result, it has been a challenging job for instructors teaching curves and surfaces in computer graphics, computer aided design, and other related courses. During past years, there have not been very many efforts dedicated to curve design tool development. Yen [7] produced a well-received video program explaining important concepts of B-spline curves and surfaces and Rockwood and Chambers [6] published a multimedia tutorial on computer aided geometric design. The former only provides a one-way communication, while the latter restricts users to a predefined environment with very limited interaction for users to carry out experiments. To fill this gap, our tool provides students with a fully interactive environment in which they are free to design, modify, and manipulate curved objects and perform experiments without constraints.In the following, Section 2 presents design issues, Section 3 discusses general features, Section 4 enumerates basic elements, Section 5 covers advanced topics, and Section 6 is our conclusion. Interested readers should consult [1, 2, 5] for mathematical background details.
6260525
Teaching surface design made easy
All popular computer graphics textbooks have chapters on curves and surfaces [1, 5, 6, 7]. Teaching these chapters could be one of the most challenging tasks in a computer graphics course because of the involved mathematics and the difficulty of visualizing the anticipated effects of the theoretical results. We certainly can skip these chapters and only rely on the polyhedron world, because Gouraud’s or Phong’s shading algorithms could make polyhedra objects appear as realistic curvilinear ones. Unfortunately, real world applications such as ship hull and car body design are usually curvilinear and may only be approximated using polyhedron models. Thus, to address this problem and to make teaching surface design easier, we have designed a pedagogical tool as part of our NSF supported project [8]. One of our goals is to provide the students with an interactive environment which is used to visualize, experiment and verify important and fundamental concepts and algorithms. While there are good textbooks on curve and surface design [3, 4, 9], we can only find two pedagogical aids. Yen’s video program [11] only provides one way information flow. Rockwood and Chambers [10] describe a multimedia tutorial on computer aided geometric design which runs on Windows. It is basically a tutorial that introduces concepts using some animation but lacks a
5309798
Conflict Analysis Based on Discernibility and Indiscernibility
The dual notions of discernibility and indiscernibility play an important role in intelligent data analysis. While discernibility focuses on the differences, the indiscernibility reveals the similarities. By considering them together in a same framework, one is able to obtain new insight of data. The main objective of the paper is to apply discernibility and indiscernibility to conflict analysis, a theory dealing with opinions of a set of agents on a set of issues. In particular, we are interested in the problem of issue reduction, so that a reduced set of issues can be obtained without loss of crucial information of the original set of issues. Extending the results from rough set theory, three types of issue reducts are introduced. They correspond to discernibility, indiscernibility, and discernibility-and-indiscernibility reducts, respectively. The results of this paper may offer a new research direction in rough set analysis in general, and conflict analysis in particular.
10708118
Fault modeling and simulation for crosstalk in system-on-chip interconnects
System-on-chips (SOCs) using ultra deep sub-micron (DSM) technologies and GHz clock frequencies have been predicted by the 1997 SIA Road Map. Recent studies, as well as experiments reported in this paper, show significant crosstalk effects in long on-chip interconnects of GHz DSM chips. Recognizing the importance of high-speed, reliable interconnects in GHz SOCs, we address in this paper the problem of testing for glitch and delay errors caused by crosstalk in buses and interconnects between components of a SOC. Since it is not possible to explicitly test for all the possible process variations and defects that can lead to crosstalk errors in SOC interconnects, we present an abstract model, Maximum Aggressor (MA) fault model, and its test requirements. The attractiveness of the model is that it can abstract crosstalk defects in interconnects with a linear number of faults, while the corresponding MA tests provide complete coverage for all level defects related to cross-coupling capacitance the interconnects. A SPICE-level fault simulation methodology is presented which allows simulation of a small subset of the potentially exponential number of defects. The simulation methodology also enables validation of the proposed fault model and the resulting test set.
15518950
Effective and Scalable Authorship Attribution Using Function Words
Techniques for identifying the author of an unattributed document can be applied to problems in information analysis and in academic scholarship. A range of methods have been proposed in the research literature, using a variety of features and machine learning approaches, but the methods have been tested on very different data and the results cannot be compared. It is not even clear whether the differences in performance are due to feature selection or other variables. In this paper we examine the use of a large publicly available collection of newswire articles as a benchmark for comparing authorship attribution methods. To demonstrate the value of having a benchmark, we experimentally compare several recent feature-based techniques for authorship attribution, and test how well these methods perform as the volume of data is increased. We show that the benchmark is able to clearly distinguish between different approaches, and that the scalability of the best methods based on using function words features is acceptable, with only moderate decline as the difficulty of the problem is increased.
5871849
Exactly-once delivery in a content-based publish-subscribe system
This paper presents a general knowledge model for propagating information in a content-based publish-subscribe system. The model is used to derive an efficient and scalable Protocol for exactly-once delivery to large numbers (tens of thousands per broker) of content-based subscribers in either publisher order or uniform total order Our protocol allows intermediate content filtering at each hop, but requires persistent storage only at the publishing site. It is tolerant of message drops, message reorderings, node failures, and link failures, and maintains only "soft" state at intermediate nodes. We evaluate the performance of our implementation both under failure-free conditions and with fault injection.
32435431
Regularized Semi-supervised Classification on Manifold
Semi-supervised learning gets estimated marginal distribution PX with a large number of unlabeled examples and then constrains the conditional probability p(y | x) with a few labeled examples. In this paper, we focus on a regularization approach for semi-supervised classification. The label information graph is first defined to keep the pairwise label relationship and can be incorporated with neighborhood graph which reflects the intrinsic geometry structure of PX. Then we propose a novel regularized semi-supervised classification algorithm, in which the regularization term is based on the modified Graph Laplacian. By redefining the Graph Laplacian, we can adjust and optimize the decision boundary using the labeled examples. The new algorithm combines the benefits of both unsupervised and supervised learning and can use unlabeled and labeled examples effectively. Encouraging experimental results are presented on both synthetic and real world datasets.