Performance of Multicast Communication on Hypercubes

Based upon hypercube multiprocessor systems,this paper analyses in detail the communication performance under the background of the greedy multicast algorithm GMA.The mean delay time of a message both at a node and in the system under multicasting is derived.For the sake of contrast,the delay of multicast message is compared with that of multiple one-to-one messages.     

Optimal communication algorithms for hypercubes

We consider the following basic communication problems in a hypercube network of processors: the problem of a single processor sending a different packet to each of the other processors, the problem of simultaneous broadcast of the same packet from every processor to all other processors, and the problem of simultaneous exchange of different packets between every pair of processors. The algorithms proposed for these problems are optimal in terms of execution time and communication resource requirements; that is, they require the minimum possible number of time steps and packet transmissions. In contrast, algorithms in the literature are optimal only within an additive or multiplicative factor.     

Efficient parallelizable hashing using small non-compressing primitives

A well-established method of constructing hash functions is to base them on non-compressing primitives, such as one-way functions or permutations. In this work, we present \(S^r\), an \(rn\)-to-\(n\)-bit compression function (for \(r\ge 1\)) making \(2r-1\) calls to \(n\)-to-\(n\)-bit primitives (random functions or permutations). \(S^r\) compresses its inputs at a rate (the amount of message blocks per primitive call) up to almost 1/2, and it outperforms all existing schemes with respect to rate and/or the size of underlying primitives. For instance, instantiated with the \(1600\)-bit permutation of NIST’s SHA-3 hash function standard, it offers about \(800\)-bit security at a rate of almost 1/2, while SHA-3-512 itself achieves only \(512\)-bit security at a rate of about \(1/3\). We prove that \(S^r\) achieves asymptotically optimal collision security against semi-adaptive adversaries up to almost \(2^{n/2}\) queries and that it can be made preimage secure up to \(2^n\) queries using a simple tweak.     

Efficient routing schemes for multiple broadcasts in hypercubes

The authors analyze the problem in which each node of the binary hypercube independently generates packets according to a Poisson process with rate λ; each of the packets is to be broadcast to all other nodes. Assuming unit packet length and no other communications taking place, it is observed that the system can be stable in steady-state only if the load factor ρ≡λ (2^d-1)/d satisfies ρ<1 where d is the dimensionality (diameter) of the hypercube. Moreover, the authors establish some lower bounds for the steady-state average delay D per packet and devise and analyze two distributed routing schemes that are efficient in the sense that stability is maintained for all ρ<ρ* where ρ* does not depend on the dimensionality d of the network, while the average delay D per packet satisfies D⩽Kd(1+ρ) for small values of ρ (with constant K). The performance evaluation is rigorous for one scheme, while for the other the authors resort to approximations and simulations     

Optimal matrix transposition and bit reversal on hypercubes: All-to-all personalized communication

In a hypercube multiprocessor with distributed memory, messages have a street address and an apartment number, i.e., a hypercube node address and a local memory address. Here we describe an optimal algorithm for performing the communication described by exchanging the bits of the node address with that of the local address. These exchanges occur typically in both matrix transposition and bit reversal for the fast Fourier transform.     

Fast fault-tolerant parallel communication and on-line maintenance for hypercubes using information dispersal

A space-efficient Information Dispersal Algorithm (IDA) is applied to fault-tolerant parallel communication in the hypercube. LetN denote the size of the network. Our routing scheme runs in 2·logN+1 time using constant size buffers (if the routing information is not counted). Its probability of successful routing is at least 1–N ^{–2.419·logN+1.5}, proving Rabin's conjecture. The scheme runswithin the said time bound without queueing delay, and it toleratesO(N) random link failures with high probability.Optimal on-line and efficient wire maintenance on the hypercube can be realized if our fault-tolerant routing scheme is used. Let denote the total number of links in the hypercube. It is shown that a constant fraction (/352) of the wires can be disabled simultaneously without disrupting the ongoing computation or degrading the routing performance much. This property suggests various on-line maintenance procedures.This research was supported by NSF Grant MCS-8121431 at Harvard University. This paper is based on Chapters 4, 5, and 8 of the author's Ph.D. dissertation.     

Fault tolerance of hypercubes and folded hypercubes

Let \(G = (V,E)\) be a connected graph. The conditional edge connectivity \(\lambda _\delta ^k(G)\) is the cardinality of the minimum edge cuts, if any, whose deletion disconnects \(G\) and each component of \(G - F\) has \(\delta \ge k\) . We assume that \(F \subseteq E\) is an edge set, \(F\) is called edge extra-cut, if \(G - F\) is not connected and each component of \(G - F\) has more than \(k\) vertices. The edge extraconnectivity \(\lambda _\mathrm{e}^k(G)\) is the cardinality of the minimum edge extra-cuts. In this paper, we study the conditional edge connectivity and edge extraconnectivity of hypercubes and folded hypercubes.     

Efficient visual communication channels

This paper compares the efficiency of uniform quantization in the spatial domain with frequency dependent quantization in the spatial frequency domain, in the context of the end-to-end performance of visual-communication channels. Results show that the minimum data density required for informationally lossless transmission depends on the design of the image-gathering device. The information in the acquired signal, not the energy, dictates the trade-off between data transmission and visual quality. Frequency dependent quantization that maintains the information capacity of the channel while reducing the entropy of the encoded signal, improves its information efficiency. Information bit-allocation is preferable for optimized visual communication for restoration, whereas energy bit-allocation can be used only for image reconstruction.This research was supported by NASA Task Assignment NAS1-18584-90 with the Department of Mathematics, Old Dominion University, Norfolk, Virginia 23529.     

Efficient extraction of primitives from line drawings composed of horizontal and vertical lines

The performance of the algorithms for the extraction of primitives for the interpretation of line drawings is usually affected by the degradation of the information contained in the document due to factors such as low print contrast, defocusing, skew, etc. In this paper, we are proposing two algorithms for the extraction of primitives with good performance under degradation. The application of the algorithms is restricted to line drawings composed of horizontal and vertical lines. The performance of the algorithms has been evaluated by using a protocol described in the literature. Received: 6 August 1996 / Accepted: 16 July 1997     

An analysis of VI Architecture primitives in support of parallel and distributed communication

We present the results of a detailed study of the Virtual Interface (VI) paradigm as a communication foundation for a distributed computing environment. Using Active Messages and the Split‐C global memory model, we analyze the inherent costs of using VI primitives to implement these high‐level communication abstractions. We demonstrate a minimum mapping cost (i.e. the host processing required to map one abstraction to a lower abstraction) of 5.4 μs for both Active Messages and Split‐C using four‐way 550 MHz Pentium III SMPs and the Myrinet network. We break down this cost to the use of individual VI primitives in supporting flow control, buffer management and event processing and identify the completion queue as the source of the highest overhead. Bulk transfer performance plateaus at 44 Mbytes/s for both implementations are due to the addition of fragmentation requirements. Based on this analysis, we present the implications for the VI successor, Infiniband. Copyright © 2002 John Wiley & Sons, Ltd.     

Scheduling divisible jobs on hypercubes

In this work a problem of finding an optimal distribution of a divisible computational job among a set of processors is considered. In the model of parallel computer systems two important factors must be taken into account: speeds of processors and speeds of communications links. With regard to this, we propose a deterministic approach finding an optimal distribution of the job's load on a hypercube of processors. The method used allows also the determination of performance bounds on the hypercube architecture.     

Incomplete crossed hypercubes

In this paper, a new interconnection network called the incomplete crossed hypercube is proposed for connecting processors of parallel computing systems. The incomplete crossed hypercube architecture denoted by CI _n−m ⁿ is made by combining two complete crossed hypercubes CQ _n and CQ _n−m for 1≤m≤n. Several topological properties of CI _n−m ⁿ are analyzed. In particular, accurate mean internode distance formulas of both CQ _n and CI _n−m ⁿ are given. Compared with the incomplete enhanced hypercube EI _n−m ⁿ , CI _n−m ⁿ has shorter mean internode distance for large n. An optimal routing algorithm for CI _n−m ⁿ is also described which guarantees the generation of a shortest path from a node to another in CI _n−m ⁿ .     

Mapping finite element graphs on hypercubes

The two-way stripes partition mapping and the greedy assignment mapping are proposed to map finite element graphs composed of a number of rectilinear four-node elements on hypercubes. The two-way stripes partition mapping is a two-phase mapping approach. In the first phase a two-way stripes partition heuristic is used to lower the communication cost. In the second phase the load transfer heuristic is used to balance the computational load among processors. The greedy assignment mapping tries to minimize the communication cost and balance the computational load of processors simultaneously. Our simulation results show that the speedups for the two-way stripes partition mapping are better than those for the greedy assignment mapping when the load balancing criterion is achieved in both approaches (that is, the number of nodes in each processor is at most one more than the number of nodes in any other processor). However, the greedy approach performs well at a much lower cost.The work of this author was supported in part by NSF under contract CCR-9110812.     

Efficient HMAC-based secure communication for VANETs

Vehicular Ad Hoc Network (VANET) is an emerging type of network which facilitates vehicles on roads to communicate for driving safety. It requires a mechanism to help authenticate messages, identify valid vehicles, and remove malevolent vehicles which do not obey the rules. Most existing solutions either do not have an effective message verification scheme, or use the public key infrastructure (PKI). In this network, vehicles are able to broadcast messages to other vehicles and a group of known vehicles can also communicate securely among themselves. So group communication is necessary for the network. However, most existing solutions either do not consider this or use pairing operation to realize this. They are either not secure or not effective. In this paper, we provide a more comprehensive set of secure schemes with Hash-based Message Authentication Code (HMAC) in VANETs to overcome their shortcomings. Of course, we still need to use Pairing operation in some place. Our scheme is composed of three schemes: (1) Communications between Vehicles and Road-Side Units (RSUs), (2) One to One Communications within a Group, (3) One to One Communications without a Group. Based on our simulation study, we show that our schemes are effective and the delay caused is much lower. The average delay caused by our first scheme is nearly thousands of times lower than prior schemes. The average delay caused by our second scheme is 0.312 ms, while the delay caused by prior scheme is 12.3 ms. Meanwhile the average delay caused by our third scheme is 0.312 ms, and the delay caused by prior scheme is about 9 s.     

Efficient fair algorithms for message communication

A computer network serves distributed applications by communicating messages between their remote ends. Many such applications desire minimal delay for their messages. Beside this efficiency objective, allocation of the network capacity is also subject to the fairness constraint of not shutting off communication for any individual message. Processor Sharing (PS) is a de facto standard of fairness but provides significantly higher average delay than Shortest Remaining Processing Time (SRPT), which is an optimally efficient but unfair algorithm. In this paper, we explore efficient fair algorithms for message communication where fairness means that no message is delivered later than under PS. First, we introduce a slack system to characterize fair algorithms completely and develop efficient fair algorithms called Pessimistic Fair Sojourn Protocol (PFSP), Optimistic Fair Sojourn Protocol (OFSP), and Shortest Fair Sojourn (SFS). Then, we prove that a fair online algorithm does not assure minimal average delay attainable with fairness. Our analysis also reveals lower bounds on worst-case inefficiency of fair algorithms. We conduct extensive simulations for various distributions of message sizes and arrival times. During either temporary overload or steady-state operation, SFS and other newly proposed fair algorithms support SRPT-like efficiency and consistently provide much smaller average delay than PS.     

Communication efficient matrix multiplication on hypercubes

In a recent paper Fox, Otto and Hey consider matrix algorithms for hypercubes. For hypercubes allowing pipelined broadcast of messages they present a communication efficient algorithm. We present in this paper a similar algorithm that uses only nearest neighbour communication. This algorithm will therefore by very communication efficient also on hypercubes not allowing pipelined broadcast. We introduce a new algorithm that reduces the asymptotic communication cost from . This is achieved by regarding the hypercube as a set of subcubes and by using the cascade sum algorithm.     

Biologically inspired navigation primitives

Because of their apparent simplicity, Braitenberg vehicles have been extensively used in robotics on an empirical basis. However, the lack of a backing up formal theory turns their application into an educated guess of parameter tunning. This paper provides a mathematical model of Braitenberg vehicles 2 and 3 as non-linear dynamical systems, which serves as a theoretical ground to fully exploit them for robotic applications and to create animated agents in artificial life or computer games. The behaviour of the vehicles is analysed using theory of dynamical systems under general conditions, and hints on how to generate desired behaviours are given. Results show that vehicles 2 and 3 can be used to implement bio-inspired navigation like; target reaching and stimulus avoidance, which constitute a set of navigation primitives or basis for navigation behaviour. Through a new theoretical approach, this work paves the way to a proper understanding of Braitenberg vehicles and to an extension of their applicability.