We describe the simulation of a new dynamic channel assignment algorithm in FDMA/TDMA wireless networks. The algorithm relies on periodic interference measurements by each of the base stations on the inactive frequencies, so as to identify appropriate candidate channels. The adaptive nature provides automatic configuration at the time of system initialization and adaptation to system expansion and traffic patterns with spatial or temporal variations. By eliminating the manual frequency planning process inherent to today's fixed channel assignment procedures, the self-organizing capability guarantees ease of operation for service providers, while increasing both capacity and voice quality. Our simulation experiments demonstrate stability of the algorithm and confirm its self-organizing capability. They also indicate a significant decrease of call blocking and dropping and other quality-of-service improvements.

Considers the use of massively parallel architectures to execute a trace-driven simulation of a single cache set. A method is presented for the least-recently-used (LRU) policy, which, regardless of the set size C, runs in time O(log N) using N processors on the EREW (exclusive read, exclusive write) parallel model. A simpler LRU simulation algorithm is given that runs in O(C log N) time using N/log N processors. We present timings of this algorithm's implementation on the MasPar MP-1, a machine with 16384 processors. A broad class of reference-based line replacement policies are considered, which includes LRU as well as the least-frequently-used (LFU) and random replacement policies. A simulation method is presented for any such policy that, on any trace of length N directed to a C line set, runs in O(C log N) time with high probability using N processors on the EREW model. The algorithms are simple, have very little space overhead, and are well suited for SIMD implementation.>

Article Free Access Share on Experience in massively parallel discrete event simulation Authors: Albert G. Greenberg View Profile , Boris D. Lubachevsky View Profile , Li-C. Wang View Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 193–202https://doi.org/10.1145/165231.165256Published:01 August 1993Publication History 1citation218DownloadsMetricsTotal Citations1Total Downloads218Last 12 Months7Last 6 weeks1 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 SiteeReaderPDF

New methods are presented for parallel simulation of discrete event systems that, when applicable, can usefully employ a number of processors much larger than the number of objects in the system being simulated, Abandoning the distributed event list approach, the simulation problem is posed using recurrence relations.We bring three algorithmic ideas to bear on parallel simulation: parallel prefix computation, parallel merging, and iterative folding.Efficient parallel simulations are given for (in turn) the G/G/l queue, a variety of queueing networks having a global first come first served structure (e.g., a series of queues with finite buffers), acyclic networks of queues, and networks of queues with feedbacks and cycles.In particular, the problem of simulating the arrival and departure times for the first N jobs to a single G/G/l queue is solved in time proportional to N/P + log P using P processors.

New methods are presented for parallel simulation of discrete event systems that, when applicable, can usefully employ a number of processors much larger than the number of objects in the system being simulated. Abandoning the distributed event list approach, the simulation problem is posed using recurrence relations. We bring three algorithmic ideas to bear on parallel simulation: parallel prefix computation, parallel merging, and iterative folding. Efficient parallel simulations are given for (in turn) the G/G/1 queue, a variety of queueing networks having a global first come first served structure (e.g., a series of queues with finite buffers), acyclic networks of queues, and networks of queues with feedbacks and cycles. In particular, the problem of simulating the arrival and departure times for the first N jobs to a single G/G/1 queue is solved in time proportional to N/P + log P using P processors.

The problem of computing the maximum of n inputs on an asynchronous parallel computer is considered. In general, the inputs may arrive staggered in time, the number of processors available to the maximization algorithm may vary during its execution, and the number of inputs, n , may be initially unknown. Two simple, efficient algorithms to compute the maximum are presented. Each algorithm may be invoked asynchronously, as new inputs and processors arrive. Performance measures that account for the response times of the invocations are introduced, and the algorithms are analyzed under these measures.

Given a nonnegative, irreducible matrix P of spectral radius unity, there exists a positive vector π such that π = πP. If P also happens to be stochastic, then π gives the stationary distribution of the Markov chain that has state-transition probabilities given by the elements of P. This paper gives an algorithm for computing π that is particularly well suited for parallel processing. The main attraction of our algorithm is that the timing and sequencing restrictions on individual processors are almost entirely eliminated and, consequently, the necessary coordination between processors is negligible and the enforced idle time is also negligible. Under certain mild and easily satisfied restrictions on P and on the implementation of the algorithm, x(.), the vectors of computed values are proved to converge to within a positive, finite constant of proportionality of π. It is also proved that a natural measure of the projective distance of x(.) from π vanishes geometrically fast, and at a rate for which a lower bound is given. We have conducted extensive experiments on random matrices P, and the results show that the improvement over the parallel implementation of the synchronous version of the algorithm is substantial, sometimes exceeding the synchronization penalty to which the latter is always subject.

Article Simple, efficient asynchronous parallel algorithms for maximization Share on Authors: Albert G. Greenberg AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Boris D. Lubachevsky AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Andrew M. Odlyzko AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 300–308https://doi.org/10.1145/323596.323625Online:01 August 1985Publication History 1citation122DownloadsMetricsTotal Citations1Total Downloads122Last 12 Months2Last 6 weeks1 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

In this paper we implement several basic operating system primitives by using a "replace-add" operation, which can supersede the standard "test and set" and which appears to be a universal primitive for efficiently coordinating large numbers of independently acting sequential processors.We also present a hardware implementation of replace-add that permits multiple replace-adds to be processed nearly as efficiently as loads and stores.Moreover, the crucial special case of concurrent replace-adds updating the same variable is handled particularly well: If every processing element simultaneously addresses a replace-add at the same variable, all these requests are satisfied in the time required to process just one request.