We propose a new algorithm for the execution of Discrete Event System Specification (DEVS) simulations on parallel shared memory architectures. Our approach executes parallel discrete-event simulations by executing all tasks in the PDEVS simulation protocol in parallel. The algorithm works by distributing the computations among different cores on shared memory architectures. To show the benefits of our algorithm, we present the results of a set of experiments using a synthetic benchmark and a real-world scenario using two independent computer architectures. The results obtained show how our algorithm accelerates simulations up to eight times, improving previous approaches. In addition, we show that our approach scales when we increase the number of CPU-cores used.

Web search engines are complex systems deployed on large clusters of processors. With a constant growing number of users, Web search engines capacity must be frequently evaluated. Among other techniques, capacity planning methods are a good approach to estimate the amount of processors in cluster based systems, allowing data-center engineers to ensure enough computational resources are available to efficiently deal with the ever changing streams of user queries. In this paper, we present a novel capacity planning methodology that combines discrete-event simulation and classical operational analysis for open systems formulae. With this methodology, just a small fraction of deployments are evaluated to find an optimal assignment of resources given a target workload. We experimentally evaluate a simulation-based capacity planning module in combination with an OpenMP+MPI implementation of a Web search engine, that periodically evaluates its performance metrics in order to elastically adjust the amount of computational resources needed to support the current workload. Results show that the proposed methodology is able to quickly provide a new deployment configuration upon performance changes, ensuring that an strictly sufficient amount of computational resources are available to efficiently deal with users demands.

Summary The WAND processing strategy is a dynamic pruning algorithm designed for large scale Web search engines where fast response to queries is a critical service. The WAND is used to reduce the amount of computation by scoring only documents that may become part of the top‐k document results. In this paper, we present two parallel strategies for the WAND algorithm and compare their performance on GPUs. In our first strategy (named size‐based), the posting lists are evenly partitioned among thread blocks. Our second strategy (named range‐based) partitions the posting lists according to document identifier intervals; thus, partitions may have different sizes. We also propose three threshold sharing policies, named Local, Safe‐R, and Safe‐WR, which emulate the WAND algorithm global pruning technique. We evaluated our proposals with different amounts of work, from short to extra‐large queries, using single query processing and batch of queries. Results show that the size‐based strategy reports the highest speedups but at the cost of low quality of results. The range‐based algorithm retrievals the exact top‐k documents and maintains a good speedup. Moreover, both strategies are capable of scaling as the amount of work is increased. In addition, there is no significant difference in the performance of the three threshold sharing policies.

MaxScore and its variations are efficient DAAT query evaluation methods which use dynamic pruning based on the potential relevance of documents, to provide fast and precise results. These are essential characteristics for large scale search engines. In an attempt to circumvent the inherent sequential nature of DAAT strategies, we applied two parallel strategies to implement new variations of MaxScore to execute on GPUs. The first strategy splits the posting lists based on their size to share the work among thread blocks and SMs of a GPU, while the second strategy partitions the posting lists based on the range of document IDs (docIDs). In order to improve the pruning efficiency of the parallel algorithms, we also evaluated three different strategies for sharing the threshold among the processing elements. Experiments were carried out under different sizes of the postings list, and results demonstrate the viability of both strategies and their GPU-based implementations. The sizebased partitioning showed higher speedups (18×) but lower recall for retrieved documents, while the docID-based partitioning can retrieve the exact top-k documents with slightly lower speedups (16×). Threshold sharing demonstrated significant performance gains for long postings lists. As novelty and contribution, to the best of our knowledge, this is the first parallelization of MaxScore for GPUs. Results show that our strategies are suitable for the parallelization of a class of DAAT strategies on GPUs.

In this paper we propose and evaluate new strategies for the parallel top-k query processing on GPUs. Our strategies are based on the document-at-a-time approach and have been implemented and tested with the WAND ranking algorithm. In our first strategy (named homogeneous), the posting lists are evenly partitioned among thread blocks. Our second algorithm, named heterogeneous, partitions the posting lists according to document identifier intervals, thus partitions may have different sizes. We also propose three threshold sharing policies, named Local, Safe-R and Safe-WR, which emulate the WAND algorithm global pruning technique. We evaluated our proposals using AND/OR queries, and the results show that the homogeneous algorithm allows better speedups through higher occupancy of the SMs, but at the cost of a lower recall. The heterogeneous algorithm produces the exact top-k documents and shows promising speedups. Also, the Shared-R and Shared-WR policies for threshold propagation allowed better performance, provided there is enough amount of work per thread block, which proved true for queries composed of at least a few millions documents.

Computer models have been used as a bridge between parallel algorithms and hardware architectures. The Bulk-Synchronous Parallel (BSP) is a well-known computing model originally devised for distributed algorithms running on clusters of single-core processors. The Multi-BSP model, that extends the classic BSP model, was recently proposed for multi-core processors. However, this model -implemented through the MulticoreBSP-for-C library- presents some restrictions such as the explicit synchronizations between the cores, introducing some challenges on which the hardware characteristics should be taken into account to properly model the parallel algorithms. Therefore, we explore the suitability of these models for the Dell multi-core architecture. The objectives of this contribution are twofold. First, we model two different multi-core Dell architectures. Second, we show that a simple model with few parameters can be easily adapted to each Dell platform rather than complex models which tends to use tricky hardware parameters.

We studied routing protocols for Delay Tolerant Networks devised to improve the message delivery performance in natural disaster scenarios. In this paper we propose the MinVisited protocol which during the transitive path to the message destination, selects the next node based on two features: (1) the most distant neighbor, and (2) the largest number of encounters with the destination node of the message. We compare our protocol with well-known protocols of the technical literature. The results show that the proposed protocol presents a low workload overhead with a number of hops lower than 2, and in average 95% of the messages are successfully delivered.

Summary Discrete Event System Specification (DEVS) is a formalism for the modeling and analysis of discrete event systems. Parallel DEVS (PDEVS) is an extension of DEVS for supporting Parallel and Discrete Event Simulation, which is a powerful tool for evaluating the performance of large scale systems. In this work, we propose an optimistic approximate and semi‐asynchronous parallel strategy. The level of optimism is efficiently managed throughout the simulation execution, and it is automatically adjusted based on the simulation evolution. Load balance and model partitioning is automatically made by means of an algorithm that takes advantage of the communication pattern of the simulated model. Our proposal is designed for Web search engines, which are complex and highly optimized systems devised to operate on large clusters of processors and dealing with dynamic and unpredictable user query bursts. The results show that our proposal is able to reduce both execution times and memory usage of standard optimistic simulations of Web search engine models, at the expense of small errors.

Since its inception in 2004, MapReduce has revealed as a paramount platform and disruptive technology for the execution of high performance applications that process very large volumes of data. Hadoop is one of the most popular and widely adopted open source MapReduce implementation. Companies that execute large applications over hundreds or thousands of machines every day spend large efforts in performance tuning and optimization to reduce infrastructure costs. However, the framework has around 190 parameters which can be adjusted in a large number of different configurations that can significantly impact the performance of applications. The task of optimizing Hadoop parameters requires deep knowledge about a myriad platform details. In this paper, we propose and evaluate the use of derivative-free (DFO) methods for the automatic setup of Hadoop parameters to optimize the performance of applications. DFO methods provide a simple and efficient manner for automatic optimization of Hadoop MapReduce programs. Parameter changes are deployed through DevOps tools which are used to efficiently reconfigure the cluster according to DFO decisions. In the best scenario in our experiments, the automatic optimization leads to a reduction of 71% in the execution time over the default setup of parameters (i.e., an acceleration of 3.5 times) on a cluster of 28 nodes with very low overhead for production environments. Such results show that DFO methods and automatic optimization provide a promising tool for optimizing performance and reduction of costs for Hadoop applications which do not present dramatic variation in their behavior in daily production environments.

Summary Data abundance poses the need for powerful and easy‐to‐use tools that support processing large amounts of data. MapReduce has been increasingly adopted for over a decade by many companies, and more recently, it has attracted the attention of an increasing number of researchers in several areas. One main advantage is that the complex details of parallel processing, such as complex network programming, task scheduling, data placement, and fault tolerance, are hidden in a conceptually simple framework. MapReduce is supported by mature software technologies for deployment in data centers such as Hadoop. As MapReduce becomes popular for high‐performance applications, many questions arise concerning its performance and efficiency. In this paper, we demonstrated formally lower bounds on the isoefficiency function for MapReduce applications, when these applications can be modeled as BSP jobs. We also demonstrate how communication and synchronization costs can be dominant for MapReduce computations and discuss the conditions under which such scalability limits are valid. To our knowledge, this is the first study that demonstrates scalability bounds for MapReduce applications. We also discuss how some MapReduce implementations such as Hadoop can mitigate such costs to approach linear, or near‐to‐linear speedups. Copyright © 2015 John Wiley & Sons, Ltd.

DEVS is a formalism for modeling and analysis of discrete event systems. PDEVS is an extension of DEVS for supporting Parallel and Discrete Event Simulation (PDES). PCD++ is a simulation platform that supports parallel simulations of DEVS models, where the model component allocation in processors is not an automatic process. This can be a time consuming task requiring knowledge of communication patterns among model components. In this paper, we propose and evaluate different allocation strategies devised to improve load balance of parallel DEVS simulations. The experimentation is made on a Web search engine application whose workload is featured by dynamic and unpredictable user query bursts, and high message traffic among processors.

Digital image processing consists of a set of techniques for contrast enhancement, noise reduction, image sharpening, segmentation, object recognition, and quantitative analysis of the image. In this work, we focus on object recognition on images containing electronic resistors. Our system classifies those resistors according to the colored bands of the resistors found in the image. This paper will introduce the system, presenting an architecture that leads to a high performance image processing system and describing a hybrid programming model, through the combined operation of processes and threads to meet the requirements of that system. In addition, the paper presents some discussion about the performance on different resources configuration on a cluster of multi-core nodes.

This paper proposes using Coloured Petri Nets to model performance of vertical search engines for Web search. In such systems, queries submitted by users or client systems are handled by different components implemented as services deployed on large clusters of dedicated processors. We propose models that represent key features of components running time cost at a suitable level of detail. A comprehensive evaluation study is presented to reveal good precision of models when compared against actual implementations and complex process-oriented simulators of the same search engine instances. A C++ class library is proposed to enable rapid model construction by using a hierarchical and scalable approach, and to enable transparent generation and efficient execution of respective simulation programs either sequentially or in parallel.

Large scale Web search engines are complex and highly optimized systems devised to operate on dedicated clusters of processors. Any, even a small, gain in performance is beneficial to economical operation given the large amount of hardware resources deployed in the respective data centers. Performance is fully dependent on users behavior which is featured by unpredictable and drastic variations in trending topics and arrival rate intensity. In this context, discrete-event simulation is a powerful tool either to predict performance of new optimizations introduced in search engine components or to evaluate different scenarios under which alternative component configurations are able to process demanding workloads. These simulators must be fast, memory efficient and parallel to cope with the execution of millions of events in small running time on few processors. In this paper we propose achieving this objective at the expense of performing approximate parallel simulation.

Web search engines are systems devised to cope with highly dynamic and demanding query rates. These systems are composed by several services, each one dedicated to execute a single operation required to solve a query. Services are allocated into thousand of multi-core processors organized in racks. Some services communicate more than others, so it is desirable to put them in the same rack. In this work, we present and evaluate deployment algorithms for a web search engine. In particular, we focus on vertical search engines with specific on-line content which may include shopping, advertisement, etc.. Our goal is to improve the performance of a search engine by reducing communication time. Communication among services is performed by means of a fast and complex network supporting parallel sending and receiving of messages. We propose a communication-graph-based method, in which processors are the nodes of the graph and communication between them is represented as weighted arcs. Results show that our proposal method is able to reduce maximum query response time.

Metric-space similarity search has been proven suitable for searching large collections of complex objects such as images. A number of distributed index data structures and respective parallel query processing algorithms have been proposed for clusters of distributed memory processors. Previous work has shown that best performance is achieved when using global indexing as opposed to local indexing. However global indexing is prone to performance degradation when query load becomes unbalanced across processors. This paper proposes a query scheduling algorithm that solves this problem. It adaptively load balances processing of user queries that are dynamically skewed towards particular sections of the distributed index. Sections highly hit by queries can be kept replicated. Experimental results show that with 1%-10% replication performance improves significantly (e.g., 35%) under skewed work-loads.

Large Web search engines are constructed as a collection of services that are deployed on dedicated clusters of distributed-memory processors. In particular, efficient user query throughput heavily relies on using result cache services devoted to maintaining the answers to most frequent queries. Load balancing and fault tolerance are critical to this service. This paper proposes the design of a result cache service based on consistent hashing and a strategy for enabling fault tolerance. Performance evaluation is performed by using actual queries from a commercial search engine. The results show that the proposed cache service outperforms baseline approaches, decreases the average query response time, increases query throughput and efficiently recovers performance after processor failures.

This paper proposes a cache hierarchy that enables Web search engines to efficiently process user queries. The different caches in the hierarchy are used to store pieces of data which are useful to solve frequent queries. Cached items range from specific data such as query answers to generic data such as segments of index retrieved from secondary memory. The paper also presents a comparative study based on discrete-event simulation and bulk-synchronous parallelism. The studied performance metrics include overall query throughput, single-user query latency and power consumption. In all cases, the results show that the proposed cache hierarchy leads to better performance than a baseline approach built on state of the art caching techniques.

This paper studies the problem of distributing a metric-space search index based on compact clustering onto a set of distributed memory processors. The aim is enabling efficient similarity search in large-scale Web search engines. The index data structure is composed of a set of clusters enclosing the database objects and we propose distribution methods based on two different solution approaches. The first one makes use of specific knowledge about the work-load generated by user queries. Here the challenge is how to represent and use such a knowledge into a method capable of producing a cluster distribution leading to high performance. The second one follows a novel direction by completely disregarding user behavior to look instead at the relationships among the index clusters themselves to decide their placement onto processors. Both methods perform efficiently depending on the context and they are generic enough to be applied to different distributed index data structures for metric-space databases.

This paper proposes a strategy to organize metric-space query processing in multi-core search nodes as understood in the context of search engines running on clusters of computers. The strategy is applied in each search node to process all active queries visiting the node as part of their solution which, in general, for each query is computed from the contribution of each search node. When query traffic is high enough, the proposed strategy assigns one thread to each query and lets them work in a fully asynchronous manner. When query traffic is moderate or low, some threads start to idle so they are put to work on queries being processed by other threads. The strategy solves the associated synchronization problem among threads by switching query processing into a bulk-synchronous mode of operation. This simplifies the dynamic re-organization of threads and overheads are very small with the advantage that the overall work-load is evenly distributed across all threads.

This paper proposes a strategy to reduce the amount of hardware involved in the solution of search engine queries. It proposes using a secondary compact cache that keeps minimal information stored in the query receptionist machine to register the processors that must get involved in the solution of queries which are evicted from the standard result cache or are not admitted in it. This cache strategy produces exact answers by using very few processors.

Searching for similar objects in metric-space databases can be efficiently solved by using index data structures. A number of alternative sequential indexes have been proposed in the literature. This paper proposes the parallelization of a recent pivot-based index data structure which can efficiently accommodate on-line updates and reduces the number of object-to-object comparisons during searches. We present algorithms for index construction and query processing.

We present a general method of parallel query processing that allows scalable performance on distributed inverted files. The method allows the realization of a hybrid that combines the advantages of the document and term partitioned inverted files.