Machine learning has been gaining traction in recent years to meet the demand for tools that can efficiently analyze and make sense of the ever-growing databases of biomedical data in health care systems around the world. However, effectively using machine learning methods requires considerable domain expertise, which can be a barrier of entry for bioinformaticians new to computational data science methods. Therefore, off-the-shelf tools that make machine learning more accessible can prove invaluable for bioinformaticians. To this end, we have developed an open source pipeline optimization tool (TPOT-MDR) that uses genetic programming to automatically design machine learning pipelines for bioinformatics studies. In TPOT-MDR, we implement Multifactor Dimensionality Reduction (MDR) as a feature construction method for modeling higher-order feature interactions, and combine it with a new expert knowledge-guided feature selector for large biomedical data sets. We demonstrate TPOT-MDR's capabilities using a combination of simulated and real world data sets from human genetics and find that TPOT-MDR significantly outperforms modern machine learning methods such as logistic regression and eXtreme Gradient Boosting (XGBoost). We further analyze the best pipeline discovered by TPOT-MDR for a real world problem and highlight TPOT-MDR's ability to produce a high-accuracy solution that is also easily interpretable.

Virtual Machines (VM) offer data-center and cloud owners the option to lease computational resources such as CPU cycles, Memory, Disk space and Network bandwidth to end-users. Optimal usage of the resources of the Physical Machines (PM) that make up the cloud is an important consideration as a lot of major enterprises and institutions are opting for servers in the cloud. At any given time, the PMs should not be overloaded to meet SLO requirements and at the same time a minimum number of PMs should be running to conserve energy. The resource loads on individual VMs in the data center are not arbitrary. Finding patterns in the loads can help the data center owners arrange the VMs on the PMs such that both of the above requirements are met. In this paper we present a fast, low overhead, framework that intelligently predicts the behavior of the cluster based on its history and then accordingly re-distributes VMs in the cluster to free up PMs. These PMs are then re-purposed to accommodate more VMs or turned off to save energy. We analyze real world loads and show that they follow a Chaotic time series. At the core of our framework are concepts of Chaos Theory with optimizations that make our framework indifferent to the type of loads and inherent cycles in them. We set up this framework on our testbed cluster and analyze its performance. Extensive experimental results for a variety of real world loads, indicate our framework's efficacy compared to other methods reported to date.

Virtual Machines (VM) offer data center owners the option to lease computational resources like CPU cycles, Memory, Disk space and Network bandwidth to end-users. An important consideration in this scenario is the optimal usage of the resources (CPU cycles, Memory, Block I/O and Network Bandwidth) of the physical machines that make up the cloud or 'machine-farms'. At any given time, the machines should not be overloaded (to ensure certain QoS requirements are met) and at the same time a minimum number of machines should be running (to conserve energy). The loads on individual VMs residing on these machines is, in fact, not absolutely random. Certain patterns can be found that can help the data center owners arrange the VMs on the physical machines such that both of the above conditions are met (minimum number of machines running without any being overloaded). In this work we propose a framework, PoWER that tries to intelligently predict the behavior of the cluster based on its history and then accordingly distributes VMs in the cluster and turns off unused Physical Machines, thus saving energy. Central to our framework are concepts of Chaos Theory that make our framework indifferent to the type of loads and inherent cycles in them as opposed to other current prediction algorithms. We also test this framework on our testbed cluster and analyze its performance. We demonstrate that PoWER performs better than another FFT-based time series method in predicting VM loads and freeing resources on Physical Machines for our test loads.

SUMMARY Caching web pages is an important part of web infrastructures. Medium to large‐scale infrastructures deploy a cluster of servers to solve the scalability and storage problems inherent in caching. In this paper we present dynamic information‐based scalable hashing that evenly hashes client requests to a cluster of cache servers, resulting in performance scalability. Runtime information is used to determine when and how to cache pages. Cached pages are stored and retrieved mutually exclusively to/from all the servers to minimize the use of storage, resulting in storage scalability. We set up an experimental environment consisting of various machines, including client servers, a cluster of 16 cache servers, and a load balancer. We demonstrate through experimental results that dynamic information‐based scalable hashing maximizes both performance scalability and storage scalability while the existing approaches do only either one of the two. Copyright © 2011 John Wiley & Sons, Ltd.

Abstract Dispatching a large number of dynamically changing requests directly to a small number of servers exposes the disparity between the requests and the machines. In this paper, we present a novel approach that dispatches requests to servers through virtual machines, called Dispatching Requests Indirectly through Virtual Environment (DRIVE). Client requests are first dispatched to virtual machines that are subsequently dispatched to actual physical machines. This buffering of requests helps to reduce the complexity involved in dispatching a large number of requests to a small number of machines. To demonstrate the effectiveness of the DRIVE framework, we set up an experimental environment consisting of a PC cluster and four benchmark suites. With the experimental results, we demonstrate that the use of virtual machines indeed abstracts away the client requests and hence helps to improve the overall performance of a dynamically changing computing environment. Copyright © 2009 John Wiley & Sons, Ltd.

Dispatching a large number of dynamically changing requests directly to a small number of servers exposes disparity between the requests and the machines. In this paper we present a novel approach that dispatches requests to servers through virtual machines, called dispatching requests indirectly through virtual environment (DRIVE). Client requests are first dispatched to virtual machines which are subsequently dispatched to actual physical machines. This buffering of requests helps reduce the complexity involved in dispatching a large number of requests to a small number of machines. To demonstrate the effectiveness of the DRIVE framework, we set up an experimental environment consisting of a PC cluster and four benchmark suites. With the experimental results we demonstrate that use of virtual machines indeed abstracts away the client requests and hence helps improve the overall performance of a dynamically changing computing environment.

Dynamic migration of virtual machines on a cluster of physical machines is designed to maximize resource utilization by balancing loads across the cluster. When the utilization of a physical machine is beyond a fixed threshold, the machine is deemed overloaded. A virtual machine is then selected within the overloaded physical machine for migration to a lightly loaded physical machine. Key to such threshold-based VM migration is to determine when to move which VM to what physical machine, since wrong or inadequate decisions can cause unnecessary migrations that would adversely affect the overall performance. We present in this paper a learning framework that autonomously finds and adjusts thresholds at runtime for different computing requirements. Central to our approach is the previous history of migrations and their effects before and after each migration in terms of standard deviation of utilization. We set up an experimental environment that consists of extensive real world benchmarking problems and a cluster of 16 physical machines each of which has on average eight virtual machines. We demonstrate through experimental results that our approach autonomously finds thresholds close to the optimal ones for different computing scenarios and that such varying thresholds yield an optimal number of VM migrations for maximizing resource utilization.

Sort can be speeded up on parallel computers by dividing and computing data individually in parallel. Bitonic sorting can be parallelized, however, a great portion of execution time is consumed due to O(log/sup 2/P) time of data exchange of N/P keys where P, N are the number of processors and keys, respectively. This paper presents an efficient way of data communication in bitonic sort to minimize the interprocessor communication and comparison time. Before actual data movement, each pair processor exchanges the minimum and maximum in its list of keys to determine which keys are to be sent to its partner. Very often no keys need to exchange, or only a fraction of them are exchanged. At least 20% or greater of execution time could be reduced on the T3E computer in our experiments. We believe the scheme is a good way to shorten the communication time in similar applications.

This report explicates the communication overlapping capabilities of three distributed-memory machines, SGI/Cray T3E, IBM SP-2 with wide nodes, and the ETL EM-X. Bitonic sorting and Fast Fourier Transform are selected for experiments. Various message sizes are used to determine when, where, how much and why the overlapping takes place. Experimental results with up to 64 processors indicated that the communication performance of EM-X is insensitive to various message sizes while SP-2 is the most sensitive. T3E stayed in between. The EM-X gave the highest communication overlapping capability while T3E did the lowest. The experimental results are compared with the analytical results based on LogP and LogGP communication models.

Radix sort suffers from the unequal number of input keys due to the unknown characteristics of input keys.We present in this report a new radix sorting algorithm, called balanced radix sort which guarantees that each processor has exactly the same number of keys regardless of the data characteristics.The main idea of balanced radix sort is to store any processor which has over n/P keys to its neighbor processor, where n is the total number of keys and P is the number of processors.We have implemented balanced radix sort on two distributed-memory machines IBM SPZWN and Cray T3E.Multiple versions of 32-bit and 64-bit integers and 64-bit doubles are implemented in Message Passing Interface for portability.The sequential and parallel versions consist of approximately 50 and 150 lines of C code respectively including parallel constructs.Experimental results indicate that balanced radix sort can sort OSG integers in 20 seconds and 128M doubles in 15 seconds on a 64-processor SPZWN while yielding over 40-fold speedup.When compared with other radix sorting algorithms, balanced radix sort outperformed, showing two to six times faster.When compared with sample sorting algorithms, which are known to outperform all similar methods, balanced radix sort is 30% to 100% faster based on the same machine and key initialization.

Computational science problems with adaptive meshes involve dynamic load balancing when implemented on parallel machines. This dynamic load balancing requires fast partitioning of computational meshes at run time. We present in this report a scalable parallel dynamic partitioner, called S-HARP. The underlying principles of S-HARP are the fast feature of inertial partitioning and the quality feature of spectral partitioning. S-HARP is a universal dynamic partitioner with three distinctive features: (a) fast partitioning from scratch with a global view, requiring no information from the previous iterations, (b) no restriction on the issue of one partition per processor, (c) no imbalance factor issue because of precise bisection using sorting. Two types of parallelism have been exploited in S-HARP, fine-grain loop-level parallelism and coarse-grain recursive parallelism. The parallel partitioner has been implemented in Message Passing Interface on Cray T3E and IBM SP2 for portability. Experimental results indicate that S-HARP can partition a mesh of over 100,000 vertices into 256 partitions in 0.18 seconds on a 64-processor Cray T3E. S-HARP is much more scalable than other dynamic partitioners, giving over 17-fold speedup on 64 processors while ParaMeTiS1.0 gives a few-fold speedup. Experimental results demonstrate that S-HARP is three to 15 times faster than the other dynamic partitioners on computational meshes of size over 100,000 vertices while giving comparable edge cuts.

Partitioningunstructured graphsis central to the parallel solution of computational science and engineering problems, Spectral partitioners, such recursive spectral bisection (RSB), have proven effective in generating high-quality partitions of realistically-sized meshes.The major problem which hindered their widespread use was their long execution times.This paper presents a new inertial spectral partitioned, called HARP.The main objective of the proposed approach is to quickly partition the meshes at runtime in a manner that works efficiently for real applications in the context of distributed-memory machines.The underlying principle of HARP is to find the eigenvectors of the unpartitioned vertices and then project them onto the eigenvectors of the originaJ mesh.Results for various meshes ranging in size from 1000 to 100,000 vertices indicate that HARP can indeed partition meshes rapidly at runtime, Experimental results show that our largest mesh can be partitioned sequentially in only a few seconds on an SP2 which is several times faster than other spectral partitioners while maintaining the solution quality of the proven RSB method.A parallel MPI version of HARP has also been implemented on IBM SP2 and Cray T3E.PrrralIel HARP, running on 64 processors SP2 and T3E, can partition a mesh containing more than 100,000 vertices into 64 subgrids in about half a second.These results indicate that graph partitioning can now be truly embedded in dynamically-changing real-world applications,

Article Fine-grain multithreading with the EM-X multiprocessor Share on Authors: Andrew Sohn Computer and Information Science Dept., New Jersey Institute of Technology, Newark, NJ Computer and Information Science Dept., New Jersey Institute of Technology, Newark, NJView Profile , Yuetsu Kodama Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile , Jui Ku Computer and Information Science Dept., New Jersey Institute of Technology, Newark, NJ Computer and Information Science Dept., New Jersey Institute of Technology, Newark, NJView Profile , Mitsuhisa Sato Real World Computing Tsukuba Research Center, Tsukuba, Ibaraki, 305, Japan Real World Computing Tsukuba Research Center, Tsukuba, Ibaraki, 305, JapanView Profile , Hirofumi Sakane Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile , Hayato Yamana Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile , Shuichi Sakai Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile , Yoshinori Yamaguchi Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, Japan Computer Architecture Section, Electrotechnical Laboratory, Tsukuba-shi, Ibaraki 305, JapanView Profile Authors Info & Claims SPAA '97: Proceedings of the ninth annual ACM symposium on Parallel algorithms and architecturesJune 1997 Pages 189–198https://doi.org/10.1145/258492.258511Online:01 June 1997Publication History 7citation121DownloadsMetricsTotal Citations7Total Downloads121Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Solving the hard Satisfiability Problem is time consuming even for modest-sized problem instances. Solving the Random L-SAT Problem is especially difficult due to the ratio of clauses to variables. This report presents a parallel synchronous simulated annealing method for solving the Random L-SAT Problem on a large-scale distributed-memory multiprocessor. In particular, we use a parallel synchronous simulated annealing procedure, called Generalized Speculative Computation, which guarantees the same decision sequence as sequential simulated annealing. To demonstrate the performance of the parallel method, we have selected problem instances varying in size from 100-variables/425-clauses to 5000-variables/21,250-clauses. Experimental results on the AP1000 multiprocessor indicate that our approach can satisfy 99.9 percent of the clauses while giving almost a 70-fold speedup on 500 processors.

Dynamic mesh adaption on unstructured grids is a powerful tool for efficiently computing unsteady problems to resolve solution features of interest. Unfortunately, this causes load imbalance among processors on a parallel machine. This paper describes the parallel implementation of a tetrahedral mesh adaption scheme and a new global load balancing method. A huristic remapping algorithm is presented that assigns partitions to processors such that the redistribution cost is minimized. Results indicate that the paralel performance of the mesh adaption code depends on the nature of the adaption region and show a 35.5X speedup on 64 processors when about 35% of the mesh is randomly adapted. For large-scale scientific computations, our load balancing strategy gives almost a sixfold reduction in solver execution times over non-balanced loads. Furthermore, our heuristic remapper yields processor assignments that are less than 3% off the optimal solutions but requries only 1% of the computational time.

The computational requirements for an adaptive solution

Simulated annealing is known to be an efficient method for combinatorial optimization problems. Its usage for realistic problem size, however, has been limited by the long execution time due to its sequential nature. This report presents a practical approach to synchronous simulated annealing for massively parallel distributed-memory multiprocessors. We use an n-ary speculative tree to execute n different iterations in parallel on n processors, called generalized speculative computation (GSC). Execution results of the 100- to 500-city traveling salesman problems on the AP1000 massively parallel multiprocessor demonstrate that the GSC approach can be an effective method for parallel simulated annealing as it gave over 20-fold speedup on 100 processors.>

Simulated annealing is known to be highly sequential due to loop-carried dependencies. This report presents a new approach to parallel simulated annealing, called generalized speculative computation (GSC). We use an n-ary speculative tree and loop indices to execute n iterations in parallel on n processors while maintaining the same decision sequence as sequential simulated annealing. To verify the performance of GSC, we implement 100- to 500-city Traveling Salesman Problems on the AP1000 massively parallel multiprocessor. Execution results demonstrate that the GSC approach can indeed be an effective method for simulated annealing. We obtain over 20-fold speedup for the initial temperature of 0.1 and 11-fold speedup for the initial temperature of 10, all on 100 processors.

Numeric scientific problems have been the main focus of supercomputing as their numerous implementations on various multiprocessors indicate. Nonnumeric problems on the other hand have received very little attention for parallel implementation due to their irregular behaviors and a large amount of resource usage. This report presents our experiences implementing difficult nonnumeric problems on the EM-4 multiprocessor, believing that supercomputers should also be able to effectively execute nonnumeric problems if they are to be considered 'supercomputers'. We selected two typical search problems, the Eight-Puzzle and the Tower-of-Hanoi. Two parallel search techniques we used to implement the search problems, unidirectional and bidirectional heuristic search. A total of eight different programs have been implemented on the EM-4 multiprocessor with realistic problem sizes. Execution results demonstrate that the parallel bidirectional heuristic search can solve the tree depth 20 to 40 of the Eight-Puzzle in an optimal or near optimal number of iterations in less than two seconds, and is highly scalable as it gives over 40-fold speedup for both problems on 80 processors.>

Much effort has been expended on developing special architectures dedicated to the efficient execution of problems in artificial intelligence (AI), especially production systems. While artificial neural networks (ANNs) offer the promise of solving various problems in pattern recognition and classification, we demonstrate here that the ANN approach can be applied to the AI production system paradigm. Among various types of neural networks, the three-layers of ring-structured feedback network is considered in this paper to suit the problem domain under investigation. Characteristics of the production system paradigm are identified. Various aspects of the use of feedback neural networks in mapping production systems are discussed. Two types of representation techniques are studied: local and hierarchical representations. A hierarchical representation derives features from patterns in production systems and constructs a 3-dimensional space called feature space, where a pattern can be uniquely defined by a vector. To demonstrate the efficient use of the neural network approach, a mapping of the generic production system is detailed throughout the paper. The results of a deterministic simulation demonstrate that the three layers of ring-structured feedback neural network architecture can be an efficient processing mechanism for the AI production system paradigm.

Much effort has been expended on developing special architectures dedicated to the efficient execution of production systems. While data-flow principles of execution offer the promise of high programmability for numerical computations, it is shown that the data-driven principles can also be applied to symbolic computations. In particular, a mapping of the RETE match algorithm along the line of production systems is considered. Bottlenecks of the RETE match algorithm in a multiprocessor environment are identified and possible solutions are suggested. The modifications to the actor set as well as the program graph design are shown for execution on the tagged data-flow computer. The results of a deterministic simulation of this multiprocessor architecture demonstrate that artificial intelligence production systems can be efficiently mapped on data-driven architectures.>