Scheduling nonlinear computational loads

Author

Hung, Jui Tsun ; Robertazzi, Thomas G.

Author_Institution

Stony Brook Univ., Stony Brook, NY

Volume

44

Issue

3

fYear

2008

fDate

7/1/2008 12:00:00 AM

Firstpage

1169

Lastpage

1182

Abstract

A scheduling model for a tree network is studied where the computation time for each node is nonlinear in the size of the assigned load. Optimal load allocation and speedup for simultaneous load distribution for a quadratic nonlinearity are obtained using simple equations. An iterative solution for sequential load distribution is presented for a nonlinearity of arbitrary power. Superlinear speedup is possible when computational complexity is nonlinear in the size of assigned loads. Aerospace applications include spectrum computation, radar and sensor data processing, and satellite image processing.

Keywords

computational complexity; iterative methods; resource allocation; scheduling; computational complexity; nonlinear computational loads; optimal load allocation; quadratic nonlinearity; scheduling model; simultaneous load distribution; superlinear speedup; tree network; Computational complexity; Computer applications; Computer networks; Image sensors; Load modeling; Nonlinear equations; Processor scheduling; Radar applications; Radar imaging; Spaceborne radar;

fLanguage

English

Journal_Title

Aerospace and Electronic Systems, IEEE Transactions on

Publisher

ieee

Conference_Location

7/1/2008 12:00:00 AM

ISSN

0018-9251

Type

jour

DOI

10.1109/TAES.2008.4655372

Filename

4655372