Performance Evaluation of Wire-Limited Hierarchical Networks

In the study of multiprocessor networks, attention must be paid to the effects of packaging constraints on cost and performance as well as the physical hierarchy imposed by packaging. Given wiring costs and constraints, hierarchical or clustered networks are a promising approach to building multiprocessor interconnects. We examine a simple approach to clustering: local buses connect processors within a cluster, and intercluster networks such ask-aryn-cubes and generalized shuffle–exchange networks provide connections between clusters. We perform detailed queueing analysis and simulations and compare the performance of a variety of flat and clustered networks. Previously, hierarchical networks were believed to be beneficial only for traffic with good locality. Under wiring cost models, we find that hierarchical networks may have superior performance to nonhierarchical networks, even under uniform traffic (which previously was believed to be a “worst case” scenario for hierarchical topologies). Relative performance is dependent on the cost constraint used, the system configuration and message granularity. The choice of a multiprocessor interconnect must take into consideration all these factors.     

TreeMatrix: A Hybrid Visualization of Compound Graphs

We present a hybrid visualization technique for compound graphs (i.e. networks with a hierarchical clustering defined on the nodes) that combines the use of adjacency matrices, node‐link and arc diagrams to show the graph, and also combines the use of nested inclusion and icicle diagrams to show the hierarchical clustering. The graph visualized with our technique may have edges that are weighted and/or directed. We first explore the design space of visualizations of compound graphs and present a taxonomy of hybrid visualization techniques. We then present our prototype, which allows clusters (i.e. subtrees) of nodes to be grouped into matrices or split apart using a radial menu. We also demonstrate how our prototype can be used in the software engineering domain, and compare it to the commercial matrix‐based visualization tool Lattix using a qualitative user study.     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

An investigation into affective design using sorting technique and Kohonen self-organising map

In this paper, a prototype system that focuses on affective design perspective for iterative product concept development is proposed and described. The prototype system, which emphasises the solicitation of affective attributes from customers, employs a sorting technique, i.e. picture sorts, for acquiring customer's affective requirements and a hierarchical structure for representing designer's formal elements to meet customer's affective requirements in product conceptualisation. As hierarchical structure alone contains qualitative and uncertain inherence, a self-organised algorithm known as Kohonen self-organising map (SOM) neural network is employed to consolidate the relationship between affective requirements from customers and formal elements from designers so as to formulate a customer-oriented product concept. The performance of the prototype system is illustrated by using a case study on the design of a mobile hand phone.     

M<Emphasis Type="SmallCaps">l-rbf</Emphasis>: RBF Neural Networks for Multi-Label Learning

Multi-label learning deals with the problem where each instance is associated with multiple labels simultaneously. The task of this learning paradigm is to predict the label set for each unseen instance, through analyzing training instances with known label sets. In this paper, a neural network based multi-label learning algorithm named Ml-rbf is proposed, which is derived from the traditional radial basis function (RBF) methods. Briefly, the first layer of an Ml-rbf neural network is formed by conducting clustering analysis on instances of each possible class, where the centroid of each clustered groups is regarded as the prototype vector of a basis function. After that, second layer weights of the Ml-rbf neural network are learned by minimizing a sum-of-squares error function. Specifically, information encoded in the prototype vectors corresponding to all classes are fully exploited to optimize the weights corresponding to each specific class. Experiments on three real-world multi-label data sets show that Ml-rbf achieves highly competitive performance to other well-established multi-label learning algorithms.     

Compiler Support for Array Distribution on NUMA Shared Memory Multiprocessors

Management of program data to improve data locality and reduce false sharing is critical for scaling performance on NUMA shared memory multiprocessors. We use HPF-like data decomposition directives to partition and place arrays in data-parallel applications on Hector, a shared-memory NUMA multiprocessor. We describe a compiler system for automating the partitioning and placement of arrays. The compiler exploits Hectors shared memory architecture to efficiently implement distributed arrays. Experimental results from a prototype implementation demonstrate the effectiveness of these techniques. They also demonstrate the magnitude of the performance improvement attainable when our compiler-based data management schemes are used instead of operating system data management policies; performance improves by up to a factor of 5.     

Evaluating the impact of locality on the performance of large-scale SCI multiprocessors

Hierarchical ring-based multiprocessor systems are attractive and enjoy several advantages over other type of systems. They ensure unique paths between nodes, simple node interfaces and simple cross-ring connections. Furthermore, employing point-to-point links allows the system to run at high clock rate which increases bandwidth and decreases latency. This paper investigates the performance of hierarchical ring-based shared-memory multiprocessors. Rings in the hierarchy are composed of point-to-point, unidirectional links and apply the Scalable Coherent Interface (SCI) protocol. We pay special emphasis on the impact of locality on processor and interconnection design issues such as number of outstanding requests, and ring topology. We find that in order to exploit the power of hierarchical multiprocessors an accurate and appropriate model of locality must be used. Hierarchical multiprocessors that are well balanced (uniform) tend to provide lower latency and higher system throughput. For non-uniform systems, high degree of locality is required for the hierarchies to perform well. However, restricting the number of outstanding transactions per processor is important in decreasing packets latency and avoiding network contention.     

Parallel programming inPanda

Distributed systems are an alternative to shared-memory multiprocessors for the execution of parallel applications.Panda is a run-time system that provides architectural support for efficient parallel and distributed programming. It supplies fast user-level threads and a means for transparent and coordinated sharing of objects across a homogeneous network. The paper motivates the major architectural choices that guided our design. The problem of sharing data in a distributed environment is discussed, and the performance of the mechanisms provided by thePanda prototype implementation is assessed.     

On Hierarchical Diameter-Clustering and the Supplier Problem

Given a data set in a metric space, we study the problem of hierarchical clustering to minimize the maximum cluster diameter, and the hierarchical k-supplier problem with customers arriving online. We prove that two previously known algorithms for hierarchical clustering, one (offline) due to Dasgupta and Long and the other (online) due to Charikar, Chekuri, Feder and Motwani, output essentially the same result when points are considered in the same order. We show that the analyses of both algorithms are tight and exhibit a new lower bound for hierarchical clustering. Finally we present the first constant factor approximation algorithm for the online hierarchical k-supplier problem.     

Information-theoretic software clustering

The majority of the algorithms in the software clustering literature utilize structural information to decompose large software systems. Approaches using other attributes, such as file names or ownership information, have also demonstrated merit. At the same time, existing algorithms commonly deem all attributes of the software artifacts being clustered as equally important, a rather simplistic assumption. Moreover, no method that can assess the usefulness of a particular attribute for clustering purposes has been presented in the literature. In this paper, we present an approach that applies information theoretic techniques in the context of software clustering. Our approach allows for weighting schemes that reflect the importance of various attributes to be applied. We introduce LIMBO, a scalable hierarchical clustering algorithm based on the minimization of information loss when clustering a software system. We also present a method that can assess the usefulness of any nonstructural attribute in a software clustering context. We applied LIMBO to three large software systems in a number of experiments. The results indicate that this approach produces clusterings that come close to decompositions prepared by system experts. Experimental results were also used to validate our usefulness assessment method. Finally, we experimented with well-established weighting schemes from information retrieval, Web search, and data clustering. We report results as to which weighting schemes show merit in the decomposition of software systems.     

Quantitative characterization and analysis of the I/O behavior of acommercial distributed-shared-memory machine

This paper presents a unified evaluation of the I/O behavior of a commercial clustered DSM machine, the HP Exemplar. Our study has the following objectives: 1) To evaluate the impact of different interacting system components, namely, architecture, operating system, and programming model, on the overall I/O behavior and identify possible performance bottlenecks, and 2) To provide hints to the users for achieving high out-of-box I/O throughput. We find that for the DSM machines that are built as a cluster of SMP nodes, integrated clustering of computing and I/O resources, both hardware and software, is not advantageous for two reasons. First, within an SMP node, the I/O bandwidth is often restricted by the performance of the peripheral components and cannot match the memory bandwidth. Second, since the I/O resources are shared as a global resource, the file-access costs become nonuniform and the I/O behavior of the entire system, in terms of both scalability and balance, degrades. We observe that the buffered I/O performance is determined not only by the I/O subsystem, but also by the programming model, global-shared memory subsystem, and data-communication mechanism. Moreover, programming-model support can be used effectively to overcome the performance constraints created by the architecture and operating system. For example, on the HP Exemplar, users can achieve high I/O throughput by using features of the programming model that balance the sharing and locality of the user buffers and file systems. Finally, we believe that at present, the I/O subsystems are being designed in isolation, and there is a need for mending the traditional memory-oriented design approach to address this problem     

Locality of Reference in Hierarchical Database Systems

Localized information referencing is a long-known and much-exploited facet of program behavior. The existence of such behavior in the data accessing patterns produced by database management systems is not currently supported by empirical results. We present experimental results which demonstrate that in certain environments and under certain important applications, locality of reference is an undeniable characteristic of the information accessing behavior of a hierarchical database management system. Furthermore, database locality of reference is in a sense more regular, predictable, and hence, more exploitable than the localized reference activity found in programs in general. The implications of these results for the performance enhancement and workload characterization of database management systems are discussed.     

Randomised Local Search Algorithm for the Clustering Problem

We consider clustering as a combinatorial optimisation problem. Local search provides a simple and effective approach to many other combinatorial optimisation problems. It is therefore surprising how seldom it has been applied to the clustering problem. Instead, the best clustering results have been obtained by more complex techniques such as tabu search and genetic algorithms at the cost of high run time. We introduce a new randomised local search algorithm for the clustering problem. The algorithm is easy to implement, sufficiently fast, and competitive with the best clustering methods. The ease of implementation makes it possible to tailor the algorithm for various clustering applications with different distance metrics and evaluation criteria.     

An empirical approach to evaluating dependency locality in hierarchically structured software systems

In software development, especially component-based software development, dependency locality states that relevant software components should be at shorter distances than irrelevant components. This principle is used together with modularity and hierarchy to guide the design of large-scale complex software systems. In previous work, dependency locality and its correlation with design quality were studied by statically measuring the interactions between software components. This paper presents an empirical approach to evaluating the hierarchical structure of software systems through mining their revision history. Two metrics, spatial distance and temporal distance, are adapted to measure the dependencies between software components. The correlation of spatial distance and temporal distance between software components represents a factor that influences system design quality. More specially, a well designed system hierarchy should have a significant positive correlation while a non-significant positive correlation or a negative correlation would signify design flaws. In an application of this approach, we use Mantel test to study the dependency locality of six software systems from Apache projects.     

Applying agglomerative hierarchical clustering algorithms to component identification for legacy systems

Context

Component identification, the process of evolving legacy system into finely organized component-based software systems, is a critical part of software reengineering. Currently, many component identification approaches have been developed based on agglomerative hierarchical clustering algorithms. However, there is a lack of thorough investigation on which algorithm is appropriate for component identification.

Objective

This paper focuses on analyzing agglomerative hierarchical clustering algorithms in software reengineering, and then identifying their respective strengths and weaknesses in order to apply them effectively for future practical applications.

Method

A series of experiments were conducted for 18 clustering strategies combined according to various similarity measures, weighting schemes and linkage methods. Eleven subject systems with different application domains and source code sizes were used in the experiments. The component identification results are evaluated by the proposed size, coupling and cohesion criteria.

Results

The experimental results suggested that the employed similarity measures, weighting schemes and linkage methods can have various effects on component identification results with respect to the proposed size, coupling and cohesion criteria, so the hierarchical clustering algorithms produced quite different clustering results.

Conclusions

According to the experimental results, it can be concluded that it is difficult to produce perfectly satisfactory results for a given clustering algorithm. Nevertheless, these algorithms demonstrated varied capabilities to identify components with respect to the proposed size, coupling and cohesion criteria.     

Invariant testing technique for debugging a structured operating system

A large class of operating system errors may be detected by invariant testing. A debugger based on continuous online invariant testing is described. The concept is to use an idle process for invariant testing; this is not time consuming and allows runtime debugging of structured operating systems. Applications and implementation of online invariant testing are discussed, and time dependencies are presented using the prototype Most operating system on a multitasking 80286-based system as an example.     

基于混合聚类的中文词聚类

文本聚类在文本挖掘和信息检索系统中发挥着重要的作用,而词聚类是文本聚类的基础。提出了一种基于混合聚类的中文词聚类方法,它将层次聚类和概念聚类结合起来,以缩短整个聚类时间。首先对预处理后的词集进行初始聚类,然后从每个类中各取一个出现次数最多的词组成新的词集,最后对该词集进行再聚类。实验表明,这种方法有效降低了中文词聚类的时间复杂度。     

The case for reconfigurable hardware in wearable computing

Wearable computers are embedded into the mobile environment of their users. A design challenge for wearable systems is to combine the high performance required for tasks such as video decoding with the low energy consumption required to maximise battery runtimes and the flexibility demanded by the dynamics of the environment and the applications. In this paper, we demonstrate that reconfigurable hardware technology is able to answer this challenge. We present the concept and the prototype implementation of an autonomous wearable unit with reconfigurable modules (WURM). We discuss experiments that show the uses of reconfigurable hardware in WURM: ASICs-on-demand and adaptive interfaces. Finally, we present an experiment with an operating system layer for WURM.     

Designing clustered multiprocessor systems under packaging andtechnological advancements

Clustered or hierarchical interconnections have advantages when designing large scale multiprocessor systems. Earlier studies have either focused on only flat interconnections or proposed hierarchical/clustered interconnections with limited packaging and demanded performance constraints. Large systems require several levels of packaging. Packaging technologies impose various physical constraints on bisection bandwidth and channel width of a system. Pinout technologies and the capacity of packaging modules have been ignored in earlier studies, often leading to configurations that are not design-feasible. Similarly, the impact of processor and interconnect technologies on demanded performance has not been considered. We propose a new supply-demand framework for multiprocessor system design by considering packaging, processor, and interconnect technologies in an integrated manner. The elegance of this framework lies in its parameterised representation of different technologies. For a given set of technological parameters the framework derives the best configuration while considering practical design aspects like maximum board area, maximum available pinout, fixed channel width, and scalability. In order to build a scalable parallel system with a given number of processors, the framework explores the design space of flat k-ary n-cube topologies and their clustered variations (k-ary n-cube cluster-c) to derive design-feasible configurations with best system performance