摘要:

The Service Delivery Scheduling (SDS) problem is an extension of the classic Job Shop Scheduling (JSS) problem, a well-known NP-hard problem in optimization even when static data are provided. SDS extends the problem domain by introducing the notion of different classes of resources to be scheduled, each with its own scheduling and availability characteristics. The telecommunications industry provides an example domain with a need to optimize SDS on an ongoing basis for scheduling the provisioning and delivery of services to customers.

ISSN:1063-7192    

DOI:10.1080/10637199608915602

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

We present a new and elegant cycle vector space algorithm that runs inO(n2.α)steps and needsO:lpar;nn)space for enumerating all simple cycles of a planar graph withnvertices, whereαis the total number of simple cycles in the graph Unlike backtrack algorithms, cycle vector space algorithms for this problem are suitable for parallelization. A parallel version of this algorithm alone with a parallel version of Syslo'sO(n.α)step algorithm for the same problem are on an exclusive-read, exclusive-write parallel RAM model withpprocessors. The results of an implementation of our parallel algorithm on a meshconnected SIMD computer are also presented.

ISSN:1063-7192    

DOI:10.1080/10637199608915603

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

A simple but powerful method, timespace mapping, for restructuring parallel algorithms and regular arrays is discussed. It combines the index vector and the time schedule of a given parallel algorithm into a new index vector, which in turn becomes the basic building block of a new and equivalent parallel algorithm. With timespace mapping, we can avoid the complex procedure of reindexing and restructure a regular array to an equivalent one.

ISSN:1063-7192    

DOI:10.1080/10637199608915604

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

NEUCOMP2 is a parallel Neural Network Compiler for a shared-memory parallel machine. It compiles a program written as a list of mathematical specifications of Neural Network (NN) models and then translates it into a chosen target program which contains parallel codes. Performance results for character recognition problems on popular NN models are presented. The models are the backpropagation, Kohonen, Counterpropagation and ART1 network models. NEUCOMP2 was developed and run on the SEQUENT Balance 8000 computer system at PARC.

ISSN:1063-7192    

DOI:10.1080/10637199608915605

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

This paper presents two planar convex hull algorithms on linear array. The First algorithm is for the case such thatn ≤ p, wherenandpare the number of points in S and the number of processors, respectively. The algorithm runs inO(n) which is optimal. The second algorithm is designed for a general case such thatn>p.The algorithm runs inO((n/p)log(n/p)) time, which is also optimal. Both algorithms have been extended tod-dimensional mesh-connected array withO(d2n1/d) in time for the case such asn < p,and O((n/p)log(n/p) + np1/d−1) in time for the case such asn>> p andp1/>> 2, which are both optimal.

ISSN:1063-7192    

DOI:10.1080/10637199608915606

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

The application of the TAGE method to variable coefficients singularly perturbed elliptic two point boundary value problem of convection-diffusion type is studied. The derivatives are approximated both by compact fourth order differences and central differences. Numerical experiments are carried out. The solutions obtained using fourth order scheme are found to be both oscillation free and convergent for large cell Reynolds number. The parallel implementation of the TAGE method is also discussed. The TAGE method is flexible and very suitable for use on parallel computers.

ISSN:1063-7192    

DOI:10.1080/10637199608915607

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

This paper discusses the efficient implementation of iterative matrix operations on application specific processor arrays. Recursive equations, frequently met in a wide range of problems, can be solved through a new systolic structure, the Reconfigurable Systolic Torus, in almost optimal Area and Time requirements. Moreover, flexibility is maintained with no demand of complex instruction sets or extensive control units implemented inside the systolic cells. The general design together with the computation schedules are presented and the description of this new structure is gradually built towards the satisfaction of some basic predefined criteria.

ISSN:1063-7192    

DOI:10.1080/10637199608915608

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

The four point explicit decoupled group (EDG) iterative method (A. R. Abdullah, 1991) and the explicit group (EG) method (D. J. Evans and M. J. Biggins, 1982; W. Yousif and D. J. Evans, 1986) were introduced as alternative numerical methods for the solution of elliptic p.d.e.'s. These methods were found to be suitable for parallel implementation (N. M. Ali and A. R. Abdullah, 1995; D. J. Evans and W. S. Yousif, 1990). In this paper, several parallel strategies for implementation on both EDG and EG methods for solving elliptic p.d.e.'s were introduced. The computational implementation of the strategies to both EDG and EG methods for solving elliptic p.d.e.'s on a MIMD Sequent Balance 8000 parallel computer are presented and discussed.

ISSN:1063-7192    

DOI:10.1080/10637199608915609

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

We consider the special case of the two functions coarsest partitioning problem, where one of the functions is a cyclic permutation and the other arbitrary. Here we present a parallel algorithm on a CRCW PRAM that solves the above partitioning problem inO(α(n)log(β(n)))time usingO(n)processors, wherenis the set cardinality,β(n)is the number of distinct prime factors ofn,andα(n)is the sum of the exponents of the primes in the factorization ofn.In almost all cases the algorithm runs inO(loglognlogloglogn)time withnprocessors.

ISSN:1063-7192    

DOI:10.1080/10637199608915610

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

The Sieve of Eratosthenes has been recently extended by excluding, for a givenkthe multiples of the firstkprimes from the initial set. The approach developed lends itself nicely to massive parallelism. Four data layouts are presented for a massively parallel SIMD architecture. It is shown that the mapping of data directly affects the performance of the algorithm. Communication strategies are examined to see the impact on the performance of the algorithm.

ISSN:1063-7192    

DOI:10.1080/10637199608915611

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor