Search

The rapid progress of wireless communication and embedded micro-sensing MEMS technologies has made wireless sensor networks possible. A wireless sensor network normally comes a large area with many inexpensive, tiny sensor nodes, each capable of collecting, processing, and storing environmental information, and communicating with neighboring nodes. In the past, sensors are connected by wired lines. Nowadays, ad hoc networking technologies can much simplify the network formation task. Installation and configura- tion of a wireless sensor network are thus effortless. Many applications of wireless sensor networks have been proposed, including field data collection, remote monitoring and control, smart home, factory automation, security, etc.

Very few of us can imagine our lives without cellular phones and, more generally, without pervasive connections. But all of us, including those few who remain cool, are attracted by all the challenging algorithmic problems involved in obtaining connections anywhere and at any time. New levels of complex- ity, not present in the algorithmic design for wired networking, emerge. Indeed, the algorithms must optimize the use of scarce resources such as bandwidth and battery power, must deal with unreliable wireless channels as well as selfish and sometimes Byzantine partners, and must commute from one wireless sys- tem to another in a way transparent to the system users. In the above scenario, the complexity has been tamed using new clever algorithms, which are often based on those that are al- ready part of the foundations of computer science.

A hybrid scheduling that effectively combines broadcasting for very popular data (push data) and dissemination upon-request for less popular data (pull data) in asymmetric communication environments is introduced. In this solution, the server continuously broadcasts one push item and disseminates one pull item. The clients send their requests to the server, which queues-up them for the pull items. At any instant of time, the item to be broadcast is designated applying a pure-push scheduling, while the item to be pulled is the one stored in the pull-queue, which has accumulated, so far, the highest number of pending requests. The value of the average expected waiting time spent by a client in the hybrid system is evaluated analytically, and the cut-off point between push and pull items is chosen so that such a waiting time is minimized. It is found out that by doing so the cut off point decreases to a value, which is much less than the total number of items present in the system, improving upon the average waiting time spent by a client in a pure push system and also on that spent in some of the hybrid systems already proposed in literature.

Constructing parallel computing systems using multiple optical buses is a new approach for alleviating the communication bottleneck problem in parallel computing. Various processor arrays connected by reconfigurable optical buses have been proposed. Bus reconfigurability has given rise to new parallel computing models. In this paper, we introduce a new parallel architecture called Array Connected by Pipelined Optical Buses with conditional delays (ACPOB). An ACPOB is simpler than previously proposed processor arrays with optical buses; its optical buses are not reconfigurable. We show that computing prefix sums pf n binary values on an n ½ x n ½ ACPOB can be carried out in 0 (1) computation steps and O (1) bus cycles. We then present efficient algorithms for a set of fundamental problems which include data compaction, data partition, permutation routing, searching, sorting and selection. Our results indicate that an ACPOB is a powerful and realistic parallel computation model.

An abstract is not available.

Conflict-free, memory access is one of the important factors for the overall performance of a multiprocessor System in which the available memory is partitioned into several modules. Even if there is no contention in the processor-memory interconnection path, conflicts may still occur when two or more processors attempt to gain access to a single memory module or a memory location within a module. With a goal to achieve higher memory bandwidth, in this paper we resolve access conflicts at the level of memory modules. In particular, we deal with the problem of evenly mapping a data structure, called host, into as few distinct memory modules as possible to guarantee that subsets of distinct host nodes, called templates, can be accessed simultaneously in a conflict-free manner.Since trees are among the most frequently used data structures in numerous applications, we propose a simple algebraic function based on the node indices for assigning the nodes of a k-ary tree to the memory modules in such a way that each subtree of a given height and arity can be accessed without conflicts. The assignment is direct, load balanced and also optimal in terms of the number of modules required. We also investigate conflict-free access to d-dimensional subcubes (Qd) of n-dimensional hypercubes (Qn), where Qn represcnts a set of items indexed with n-digit addresses and accesses will be made to subsets of items differing in any arbitrary d-digit positions. With the help of the coding theory, we propose a novel approach to solve the subcube access problem. Codes with minimum distance d > 2 play a crucial role in our applications. We prove that any occurrence of a subcube Q, C Qn, for O < a < d - 1, can be accessed without conflicts using [2n] memory modules, by associating Qn with a linear [M]code C of length n, size M and minimum distance d. Associating the hypercube nodes with perfect or maximum distance separable (MDS) codes, our problem is solved optimally both in terms of the number of memory modules required and load balancing per module. These codes can be easily modified (without node relocation) according to the change in the sìze of the host or the number of available memory modules.

This paper analyzes the cost of performing broadcast, product and prefix computation on the ideal fat-tree, a model proposed here to capture distance and bandwidth properties common to a variety of fat-tree networks. Algorithms are developed and analyzed in terms of the capacity of channels at different levels of the fat-tree. Non trivial lower bounds are derived establishing the optimality of our algorithms for a wide range of channel capacities.

An abstract is not avaiable

In this paper, the canonical signed digit (CSD)coding and the generalized non-adjacent form (GNAF)-coding of signed integers are reduced to a prefix computation. Hence, these coding operations. Which seem at first glance strictly sequential, can be optirnally perallelized.

A Parallel Priority Queue (PPQ) is defined as an abstract data type for storing a set of integer-valued items and providing operations such as insertion of n new items or deletion of the n smallest ones. In this paper, the PPQ data type is implemented on the PRAM model of parallel computation. Two data structures are introduced, the n-Bandwidth-Heap (nH) and the n-Bandwidth-Leftist-Heap (nL), based on the well known sequential binary-heap and leftist-heap organizations, respectively. Efficient parallel algorithms are then given for the basic operations of insertion, deletion and heap construction on nH and nL, based on known parallel sorting and merging algorithms.