Relay transmission is a promising technology for improving the throughput and energy efficiency in multi-rate wireless personal area networks (WPANs). In this paper, we propose a distributed relay MAC (DR-MAC) protoco...
详细信息
ISBN:
(纸本)9780769534718
Relay transmission is a promising technology for improving the throughput and energy efficiency in multi-rate wireless personal area networks (WPANs). In this paper, we propose a distributed relay MAC (DR-MAC) protocol in WiMedia WPANs. DR-MAC extends a distributed reservation protocol (DRP) in WiMedia MAC and neighbor information for relay transmission can be collected during the beacon period. Therefore, DR-MAC can minimize control overhead for relay transmission and is compatible to the standard WiMedia MAC protocol. We also introduce a medium access slot (MAS) allocation procedure for maximizing the efficiency in DR-MAC. Compared with direct transmission, extensive simulation results demonstrate that DR-MAC can improve the throughput by 10% and reduce the energy consumption by 26% when the number of devices is 20.
Many distributed applications require the knowledge of the causality relation induced by the computation. Reconstructing this relation appears to be an interesting tool for such applications, but a vector of size S - ...
详细信息
ISBN:
(纸本)081864222X
Many distributed applications require the knowledge of the causality relation induced by the computation. Reconstructing this relation appears to be an interesting tool for such applications, but a vector of size S - where S is the number of processes - must be attached to each event to achieve this reconstruction. This induces a large overhead in secondary memory. After defining special events of the computation - some kind of checkpoints - we propose two algorithms that discard unnecessary data for the causal relationship reconstruction. The first algorithm acts on-the-fly while the second acts during reconstruction.
In this paper, we describe an extension to the A CGT GridR environment which allows the parallelization of loops in R scripts in view of their distributed execution on a computational grid. The ACGT GridR service is e...
详细信息
ISBN:
(纸本)9780769534718
In this paper, we describe an extension to the A CGT GridR environment which allows the parallelization of loops in R scripts in view of their distributed execution on a computational grid. The ACGT GridR service is extended by a component that uses a set of preprocessor-like directives to organize and distribute calculations. The use of parallelization directives as special R comments provides users with the potential to accelerate lengthy calculations with changes to preexisting code. The GridR service and its extension are developed as components of the ACGT platform, one aim of which is to facilitate the data mining of clinical trials involving large datasets. In A CGT, GridR scripts are executed in the framework of a specifically developed workflow environment, which is also briefly outlined in the present article.
Most traditional distributed Shared Memory (DSM) systems support data sharing in multi-process applications. This paper proposed a Multi-threaded Multi-home DSM system (MM-DSM) to support both data sharing and computa...
详细信息
ISBN:
(纸本)9780769537474
Most traditional distributed Shared Memory (DSM) systems support data sharing in multi-process applications. This paper proposed a Multi-threaded Multi-home DSM system (MM-DSM) to support both data sharing and computation synchronization in multi-threaded applications whose threads are grouped into bundles and distributed across multiple computers for parallel execution. Globally shared data are rearranged and assigned to different thread bundles based on their access patterns. As thread bundles move around, their hosting nodes will act as the homes of the associated data blocks to reduce communication cost. Programmers can still stick to the shared memory programming paradigm whereas data consistency, distributed lock, false sharing and multiple writes are taken care of by MM-DSM. Experimental results demonstrate its effectiveness and correctness.
Homing sequences play an important role in the testing of finite state systems and have been used in a number of applications such as hardware fault-detection, protocol verification, and learning algorithms etc. Recen...
详细信息
Homing sequences play an important role in the testing of finite state systems and have been used in a number of applications such as hardware fault-detection, protocol verification, and learning algorithms etc. Recent applications of homing sequences involve large DFA's with thousands of states. Such applications motivate the design of a parallel algorithm for this problem. Here we present a deterministic parallel algorithm of time complexity O(√nlog2n) using a polynomial number of processors on CREW PRAM model. No faster deterministic parallel algorithm is known for this problem. We also discuss the parallel complexity of some related problems.
In object oriented database, objects are connected to each other by various kinds of relationships and form a general directed graph. The idea of leveled clustering is utilized to take advantage of the relationships a...
详细信息
ISBN:
(纸本)081864222X
In object oriented database, objects are connected to each other by various kinds of relationships and form a general directed graph. The idea of leveled clustering is utilized to take advantage of the relationships and solve the problem of object allocation and storage in an distributed object oriented database. Both non-replicative and replicative algorithms are developed to allocate objects to different sites and organize them in the storage of the local databases.
Highways is a distributed-programming system, we are building, with high-performance as a major goal. The suite of send primitives implemented in Highways, called Global-Flush Primitives, have three notable aspects. (...
详细信息
ISBN:
(纸本)081864222X
Highways is a distributed-programming system, we are building, with high-performance as a major goal. The suite of send primitives implemented in Highways, called Global-Flush Primitives, have three notable aspects. (1) Global-Flush Primitives permit making an assertion about messages sent in the past of sending m, in the future of sending m, about both, or neither. (2) The past and the future of an event is defined using the relation `happened before.' (3) A message can be sent to any subgroup of processes specified as a parameter.
We propose a novel computational model for GPU. Known parallel computational models such as the PRAM model are not appropriate for evaluating GPU algorithms. Our model, called AGPU, abstracts the essence of current GP...
详细信息
ISBN:
(纸本)9781479941162
We propose a novel computational model for GPU. Known parallel computational models such as the PRAM model are not appropriate for evaluating GPU algorithms. Our model, called AGPU, abstracts the essence of current GPU architectures such as global and shared memory, memory coalescing and bank conflicts. We can therefore evaluate asymptotic behavior of GPU algorithms more accurately than known models and we can develop algorithms that are efficient on many real architectures. As a showcase, we first analyze known comparison-based sorting algorithms using the AGPU model and show that they are not I/O optimal, that is, the number of global memory accesses is more than necessary. Then we propose a new algorithm which uses an asymptotically optimal number of global memory accesses and whose time complexity is also nearly optimal.
We develop and experiment with a new parallel algorithm to approximate the maximum weight cut in a weighted undirected graph. Our implementation is based on the recent new algorithm of Goemans and Williamson for this ...
详细信息
We develop and experiment with a new parallel algorithm to approximate the maximum weight cut in a weighted undirected graph. Our implementation is based on the recent new algorithm of Goemans and Williamson for this problem. However, our work aims for an efficient, practical formulation of the algorithm with close to optimal parallelization. Our theoretical analysis and an implementation on the Connection Machine CM5 show that our parallelization achieves linear speedup. We test our implementation on several large graphs (more than 9000 vertices), particularly on large instances of the Ising model.
Local Area MultiProcessors (LAMP) is a network of personal workstations with distributed shared physical memory provided by high performance technologies such as SCI. LAMP is more tightly coupled than the traditional ...
详细信息
ISBN:
(纸本)0818675829
Local Area MultiProcessors (LAMP) is a network of personal workstations with distributed shared physical memory provided by high performance technologies such as SCI. LAMP is more tightly coupled than the traditional local area networks (LAN) but is more loosely coupled than the bus based multiprocessors. This paper presents a distributed scheduling algorithm which exploits the distributed shared memory in SCI-LAMP to schedule the idle remote processors among the requesting workstations. It considers fairness by allocating remote processing capacity to the requesting workstations based on their priorities according to the decay-usage scheduling approach. The performance of the algorithm in scheduling both sequential and parallel jobs is evaluated by simulation. It is found that the higher priority nodes achieve faster job response times and higher speedups than that of the lower priority nodes. Lower scheduling overhead allows finer granularity of remote processors sharing than in LAN.
暂无评论