PERFORMANCE CONSIDERATIONS ON A RANDOM GRAPH MODEL FOR PARALLEL-PROCESSING

 
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο



PERFORMANCE CONSIDERATIONS ON A RANDOM GRAPH MODEL FOR PARALLEL-PROCESSING (EN)

STAFYLOPATIS, A (EN)
AFRATI, F (EN)

N/A (EN)

Consider a random directed acyclic graph (dag) with nodes 1, 2, ..., n, and an edge from node i to node j (only if i >j) with fixed probability p. Such a graph can be thought of as the task graph associated with a job and thus it serves as a parallel processing model; the vertices correspond to tasks and the edges correspond to precedence constraints between tasks. In this case, the length of the graph corresponds to the parallel processing time of the job (an infinite number of available processors is assumed) and the width of the graph corresponds to the parallelism of the job. We estimate here the average length of the random dag (that is, the average processing time of the job) as a function of the probability p and the number of tasks n hy establishing tight lower and upper bounds. The lower (resp. upper) bound is determined as being equal to the average length of a random dag considerably simpler to manipulate than the original one. Furthermore, the asymptotic behaviour of the average length is studied and the results obtained improve previously published results. Finally, asymptotic results are obtained concerning the average width of the task graph; it is shown that the average width tends to 1/p as n --> infinity. (EN)

journalArticle

Random Graph Model (EN)
Parallel Processing (EN)

Εθνικό Μετσόβιο Πολυτεχνείο (EL)
National Technical University of Athens (EN)

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS (EN)

1993


DUNOD (EN)



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.