Your Search Results

Use this resource - and many more! - in your textbook!

AcademicPub holds over eight million pieces of educational content for you to mix-and-match your way.

Experience the freedom of customizing your course pack with AcademicPub!
Not an educator but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

On the number of acceptable task assignments in distributed computing systems

By: Shin, K.G.; Chen, M.-S.;

1990 / IEEE

Description

This item was taken from the IEEE Periodical ' On the number of acceptable task assignments in distributed computing systems ' A distributed computing system and cooperating tasks can be represented by a processor graph G/sub p/=(V/sub p/, E/sub p/) and a task graph G/sub T/=(V/sub T/, E/sub T/), respectively. An edge between a pair of nodes in G/sub T/ represents the existence of direct communications between the two corresponding tasks. The maximal number of hops between two processors in G/sub p/ to which two adjacent tasks in G/sub T/ are assigned is called dilation of that assignment. Characterization and use of the number of acceptable assignments for given G/sub T/ and G/sub P/ are treated. Assignments with the dilation less than or equal to one are considered. This dilation constraint represents a special case in which two adjacent tasks in G/sub T/ must be assigned to either a single processor or two adjacent processors in G/sub p/. For the case where N(G/sub T/, G/sub P/) denotes the numbers of acceptable assignments under this constraint, N(G/sub T/, G/sub P/) are derived for arbitrary G/sub T/ and G/sub P/, and a recursive expression is formulated for N(G/sub T/, G/sub P/) when G/sub T/ is a tree. For some restricted cases, either closed-form or recursive-form expressions of N(G/sub T/, G/sub P/) are derived. The results on N(G/sub T/, G/sub P/) are extended to the completely general case, assignments with dilations greater than one, where two adjacent tasks in G/sub T/ can be assigned to any two processors in G/sub P/ which are not necessarily adjacent to each other.<>