VTechWorks staff will be away for the winter holidays starting Tuesday, December 24, 2024, through Wednesday, January 1, 2025, and will not be replying to requests during this time. Thank you for your patience, and happy holidays!

Browsing by Author "Haddad, Emile K."

Now showing 1 - 20 of 20
  • Thumbnail Image
    An Algorithmic Solution to the Minimax Resource Allocation Problem with Multimodal Functions
    Dharmakadar, Aida; Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1993)
    The problem of allocation is one of the most widely investigated topics in the area of mathematical optimization because of its broad applicability to different classes of real world problems. The basic idea is that, given some type of resource whose total amount is N, we want to partition and allocate the total resource over n activities to minimize some objective function, F, whose value represents the "cost" of the allocation. As can be seen from various research results in this area, the procedures to solve discrete and continuous resource allocation problems can be significantly different. One obvious basic difference is that the discrete problem can be exactly solved by exhaustive enumeration, while the continuous problem cannot.
  • Thumbnail Image
    An algorithmic solution to the minimax resource allocation problem with multimodal functions
    Dharmakadar, Aida (Virginia Tech, 1993-09-15)
    An algorithmic approach is developed for solving the minimax continuous resource allocation problem with multimodal cost functions. Unlike previous research in the same area which developed solutions for the same problem by imposing restrictions on the cost functions, such as the assumptions of monotoniciy or convexity, this approach is applicable to problems with multimodal functions with a finite number of local extrema. Another significant advantage demonstrated by this approach is that it provides all the optimal solutions to the problem; in contrast to previous algorithms which provided a single optimal solution. When a further level of optimization using a second objective function is desired, one needs the entire set of optimal solutions as provided by the procedures of this thesis.
  • Thumbnail Image
    Analysis, Modeling and Optimization of Multiprocessing Execution Time
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1989)
    A new approach is presented for the analytical modeling of the execution times of a partitioned program running on parallel processors of a multiprocessor or distributed computed system. The model represents the execution time of the individual processors as well as the aggregate system both in the deterministic and stochastic contexts. The analytical model encompasses a broader class of multiprocessing situations and formulates a mode accurate analytical representation of the execution times than has hitherto been presented in recent literature. The representation expresses the processor execution times in terms of the program module run times, the internal intermodule communication times, interprocessor (external) times and the number of modules assigned to each processor. A criterion is derived on the optimal assignment policy for minimizing execution time, or its statistical mean in the stochastic representation.
  • Thumbnail Image
    Attainable Resource Allocation Bounds
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
    Upper and lower bounds attained by the variables of a generalized resource allocation problem are distinguished from the a priori specified bounds defining the feasible set. General theoretical criteria directly relating the attainable bounds to the specified bounds are presented, which are computationally superior to the traditional "modified simplex method". An efficient algorithm is presented, and its computational complexity is analyzed.
  • Thumbnail Image
    Attainable Resource Allocations Bounds
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1989)
    Upper and lower bounds attained by the variables of a generalized resource allocation problem are distinguished from the a priori specified bounds defining the feasible set. General theoretical criteria directly relating attainable bounds to specified bounds are presented, which are computationally superior to the traditional "modified simplex method."
  • Thumbnail Image
    A case study in object-oriented development: code reuse for two computer games
    Scott, Roger E. (Virginia Tech, 1992)
    A case study of the object-oriented development of two computer games using commercially available products was conducted. The games were constructed for use on Apple Macintosh computers using a C+ + like programming language and an accompanying object-oriented class library. Object-oriented techniques are compared with procedure oriented techniques, and benefits of object-oriented techniques for code reuse are introduced. The reuse of object-oriented code within a target domain of applications is discussed, with examples drawn from the reuse of specific functions between the two games. Other reuse topics encountered in the development effort which are discussed: reuse of operating system routines, reuse of code provided by an object-oriented class library, and reuse of code to provide functions needed for a graphical user interface.
  • Thumbnail Image
    Design and construction of a prototype general purpose syntax-aware text editor
    Faber, Joseph Lewis (Virginia Tech, 1991-05-05)
    A comparison is made between traditional text editors, syntax-directed editors and syntax-aware editors. The design for a prototype general purpose syntax-aware editor is presented. This editor utilizes a user-written language specification to continuously parse the text buffer. Errors are indicated to the user non-intrusively by modifying the display color of the text. Error messages are presented to the user as the cursor is placed over portions of the text which are in error. A description of the implementation of the editor, and a critique of its usefulness is included.
  • Thumbnail Image
    Design and performance analysis of a survivable metropolitan area fiber optic communication network
    Angeh, Wolfgang Ondua (Virginia Tech, 1990-10-02)
    The emergence of fiber optic communication technology as a viable alternative to the prevailing copper based network architectures has made it possible to capitalize on the inherent advantages of fiber which include high bandwidth, long regenerator distances and low cost. The focus of this project is to design a survivable and cost effective fiber optic communication network as a proposal for possible deployment in the city of Yaounde, Cameroon. The network comprises 100 nodes of which five are hubs, two gateways, and fourteen special central offices (COs) . It also has 141 linkS, each of them a candidate for possible fiber deployment. Computer analysis tools are used to generate an optimal topology that meets the specified route diversity constraints as well as the end-to-end DS3 demand requirements. Finally, several candidate architectures are investigated and a proposed model is selected based on how well it meets the design specifications as well as cost and survivability constraints. However, it should be noted that the final cost figures, derived from present US cost figures, will have to be adjusted to accommodate local reality and that the design methodology assumes a desert model (i.e. no pre-existing fiber conduits).
  • Thumbnail Image
    Dynamic Load Distribution Optimization in Heterogeneous MultipleProcessor Systems
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1993)
    We examine the problem of optimizing the distribution of the m interacting modules of a given work load on a parallel system with p heterogeneous processors. Average-valued parameters are used to model the intermodule coupling of the work load and its execution and communication times on the diverse system processors. We derive an analytical optimality criterion to minimize a multi-metric objective function representing a weighted combination of work load completion time, communication cost, resource utilization cost, and processor idle-time.
  • Thumbnail Image
    Dynamic Working Set Memory Allocation for Concurrent Processes
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
    The problem of allocating a given total amount of main memory page-frames M(t) available at time t, among a given set of concurrently active processes {P-sub i} is examined. Memory allocation is managed under the working set policy, and it is assumed that M(t) is larger than the total sum of all working-set sizes but less than the sum of distinct pages in {P-sub i}. It is required that each process receive at least an allocation equal to its working-set size and that the excess memory be additionally distributed among the concurrent processes to enhance their performance. The upper and lower bounds on the individual memory allocations for each process are derived. A fair policy for apportioning the excess memory among the concurrent processes is presented. A procedure for rounding off fragmented page apportionment is described. An application example, illustrating dynamically changing conditions in the concurrent active processes, is described.
  • Thumbnail Image
    The impact of network characteristics on the selection of a deadlock detection algorithm for distributed databases
    Daniel, Pamela Dorr Fuller (Virginia Tech, 1989-05-05)
    Much attention has been focused on the problem of deadlock detection in distributed databases, resulting in the publication of numerous algorithms to accomplish this function. The algorithms published to date differ greatly in many respects: timing, location, information collection, and basic approach. The emphasis of this research has been on theory and proof of correctness, rather than on practical application. Relatively few attempts have been made to implement the algorithms. The impact of the characteristics of the underlying database management system, transaction model, and communications network upon the effectiveness and performance of the proposed deadlock detection algorithms has largely been ignored. It is the intent of this study to examine more closely the interaction between a deadlock detection algorithm and one aspect of the environment in which it is implemented: namely, the communications network.
  • Thumbnail Image
    Minimax Resource Allocation with Continuous Variables: The Definitive Solution
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
    The necessary and sufficient conditions of local global optimization are derived for constrained resource allocation with continuous variables and objective functions of the forms max (sub i) {f-sub i(x-sub i)} and mini{f-sub i(x-sub i)} where {f-sub i} can be nondifferentiable, nonmonotone, nonconvex, multimodal functions. All previous theoretical results, which are sufficient conditions for global optimization with monotone {f-sub i}, are special, restrictive cases of the new criteria. The powerful criteria also enable complete determination of all the global optimal solutions, thus allowing further lexicographic optimization. The criteria also enable determination of all the local maxima and minima, a previously unaddressed facet of the solution, thus providing illuminating information on the behavior of the objective function and its overall "topography", which could be useful in suboptimal multi-criteria trade-offs. The new results admit a straightforward graphical interpretation and implementation, which facilitates their utilization and extends their applicability to practical problems where {f-sub i} are specified only in graphical formats derived from empirical or simulation data. Except for the mild and practically insignificant restrictions of continuity and "local monomodality" retained on {f-sub i} by the analysis, the results of this paper constitute the complete and definitive solution of the problem.
  • Thumbnail Image
    A model for goal oriented learning in a neural network
    Aucoin, Bryan (Virginia Tech, 1989-05-11)
    A mathematical model for goal oriented learning in a network of neuron-like elements was developed. Using a mouse/goal box analogy, a simulation of a network with four elements was programmed in Turbo Pascal, Version 4.0 (Borland International) to test the model. Each location in the network corresponded to a particular network input. The output of the network consisted of one of four behaviors: forward, backward, left or right. The network successfully learned sequences of up to six movements in increasingly complex mazes.
  • Thumbnail Image
    On the Dynamic Response of Variable-Rate, Sampled-Data Systems
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1993)
    Time-domain analysis is used to derive criteria on the stability of sampled-data feedback systems comprising a time-varying plant, a time-varying non-linearity, and a sampler which may exhibit any given periodic or aperiodic sampling mode. Three aspects of the systems dynamic response are given a unified treatment: boundedness, unboundedness, and asymptotic decay. In addition to qualitative criteria, the results provide quantitative bounds on the system response, and indicate its explicit dependence on the sampling mode.
  • Thumbnail Image
    Optimal Load Allocation for Parallel and Distributed Processing
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1989-04-01)
    The problem of minimizing the execution completion time of a given total load, to be partitioned into interacting tasks and allocated to run on a generalized model of a heterogeneous centralized or distributed multiprocessing system, is examined. The problem is formulated as a nonlinear, nonconvex nonseparable, minimax resource- allocation, continuous, mathematical programming problem. It is assumed that the quantitative functional dependence of the individual processor execution time on the partitioned load allocation is known and specified in analytical or graphical formats of a fairly general nature with no a priori restrictions of differentiability, monotonicity, convexity, and unimodality commonly imposed in previous investigations of the problem. A Theorem stating the necessary and sufficient condition for minimum concurrent processing completion time is derived. The new result represents an analytical breakthrough applicable to a wide class of hitherto analytically unsolved optimization problems in various application disciplines. The derivation starts from a precise representation of the parallel execution time and proceeds through an exact analysis that does not resort to the simplifying assumptions or analytical approximations found in analogous previous investigations. The load partitioning is considered to vary over a continuum, thus allowing the achievement of ideal optimization through one-step repartitioning of the given load. The optimization procedure determines the set of all global minimum points of the completion time function as well as all its local minima, thus allowing further lexicographic optimization and suboptimal trade-offs. The conditions of the Theorem admit a straightforward graphical interpretation which facilitates its implementation and readily extends its applicability to empirically or simulationally determined models of the system.
  • Thumbnail Image
    Query processing in heterogeneous distributed database management systems
    Bhasker, Bharat (Virginia Tech, 1992-06-06)
    The goal of this work is to present an advanced query processing algorithm formulated and developed in support of heterogeneous distributed database management systems. Heterogeneous distributed database management systems view the integrated data through an uniform global schema. The query processing algorithm described here produces an inexpensive strategy for a query expressed over the global schema. The research addresses the following aspects of query processing: (1) Formulation of a low level query language to express the fundamental heterogeneous database operations; (2) Translation of the query expressed over the global schema to an equivalent query expressed over a conceptual schema; (3) An estimation methodology to derive the intermediate result sizes of the database operations; (4) A query decomposition algorithm to generate an efficient sequence of the basic database operations to answer the query. This research addressed the first issue by developing an algebraic query language called cluster algebra. The cluster algebra consists of the following operations: (a) Selection, union, intersection and difference, which are extensions of their relational algebraic counterparts to heterogeneous databases; (b) Normal-join and normal-projection which replace their counterparts, join and projection, in the relational algebra; (c) Two new operators embed and unembed to restructure the database schema. The second issue of the query translation was addressed by development of an algorithm that translates a cluster algebra query expressed over the virtual views to an equivalent cluster algebra query expressed over the conceptual databases. A non-parametric estimation methodology to estimate the result size of a cluster algebra operation was developed to address the third issue described above. Finally, this research developed a query decomposition algorithm, applicable to the relational and non-relational databases, that decomposes a query by computing all profitable semi-join operations, followed by the determination of the best sequence of join operations per processing site. The join optimization is performed by formulating a zero-one integer linear program that uses the non-parametric estimation technique to compute the sizes of intermediate results. The query processing algorithm was implemented in the context of DAVID, a heterogeneous distributed database management system.
  • Thumbnail Image
    Scheduling of Load Balancing Across Single-Channel Broadcast Networks
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1993)
    The problem of optimizing the balancing of processing load originating at the various sites of heterogeneous processors is examined. The optimal amounts of load exchange among the sending and receiving processors are derived. The necessary and sufficient condition for the absence of synchronization delay is derived. The minimum communication capacity needed for the optimal load exchange is determined. Although not unique, the specified optimal load transfer schedule is amenable to simple implementation. Practical implementation of the specified bandwidth partitioning may employ any appropriate scheme of communication multiplexing available on the given nwork. An example with specific problem parameters is used to illustrate the determination and implementation of the optimal load transfer schedule.
  • Thumbnail Image
    A Task Scheduling Algorithm for Minimum Busiest Procesor Idle Time
    Haddad, Emile K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1993)
    This paper provides a heuristic to minimize the idle time of the busiest processor in a system in which the number of modules to be executed by every processor has been predetermined for a given precedence graph. Except for the busiest processor, the assignment of modules to the other processors is done as evenly as possible. Each of the modules involved is of unit size. An exhaustive enumeration solution of the problem is of NP-complete complexity. The heuristic presented in this paper is of polynomial time.
  • Thumbnail Image
    Token bus local area network simulator
    Guarnera, Gregg (Virginia Tech, 1991-12-15)
    This project is a token bus local area network simulator written in Pascal on an IBM PC compatible. The simulator is written for the Microsoft Windows operating environment and makes use of a graphical user interface for controlling the simulation. The program is object-oriented to make use of the Borland ObjectWindows Windows interface and because of the suitability of object-oriented programming to graphics and simulation applications. All basic token bus network functionalities specified by the Institute Of Electrical And Electronics Engineers (IEEE) 802.4 token bus standard are implemented in the simulation plus an added function to resolve duplicate node addresses. The network nodes and bus are drawn using Windows' color graphics. The state of each node is represented by text as well as the color and style each node is drawn in. The frame being transmitted is shown as large text within the bus object on the screen. The direction of data transfer on the bus is shown graphically as is the current location of the token among the nodes. The user of the simulation has the ability make any node active, inactive, or passive, or to make any node fail. The user may make a node send data to one other node or many other random nodes. The addresses of the nodes may also be changed. The user may pause, step through, or continue the simulation, control the simulation speed, control the error rate of data on the bus, and produce a lost token scenario.
  • Thumbnail Image
    A visual language for ADA program unit specifications
    Gordon, Christopher Todd (Virginia Tech, 1990-05-15)
    This thesis describes a visual programming language designed to describe and generate Ada program unit specifications. The author first describes the foundations for the work, and gives a brief introduction to some of the features of the language. Most of the thesis is dedicated to describing the visual representation for each portion of an Ada package specification. The BNF grammar of an Ada package specification is used as a basis for organization. By organizing the thesis via the package specification, all program unit specifications i.e., package, task, subprogram and generic specifications) are described and given a representation in the language. Toward the end of the thesis, the design and reference of a package specification is demonstrated in a hypothetical implementation.