Michael E. Thomadakis

Texas A&M University
College of Engineering
Department of Computer Science
Email: [email protected]

[This page is (obviously) under construction]

Hi

Take a look at the ``official'' information concerning modern Greece. There are some unofficial data, though, you may also like to study. See for instance, Greek Coasts, gogreece, webcom, Ellada, etc. There is plenty of useful information about my country and thousands of pictures worth viewing (for the day-dreaming travelers). So enjoy your journeys! Visit this excellent site, if you are interested in the prehistoric and classic Greece and its accomplishments. You can follow this link for an extensive collection of resources on Greece, from antiquity to modern days. In this site you can find information related to greek cultural history. In this site you can find several intriguing and little-known facts about Greece, its language and the journeys of Greeks through time and the big seas.
Here are a few photos from some (relatively) recent activities of the Hellenic Student Association at the Texas A&M University.

Resume

ASCII Text Resume

Research Interests

Operating Systems
Interesting information on existing research and commercial Operating Systems.
Open UNIX standard Single-UNIX Specification v2 (UNIX 98).
Collection of papers at the OSF.

Multi-Threaded
Computation Bibliography on threads and multithreading. Although somewhat dated, it is still a good starting point for articles on threads.

Deterministic
and
Stochastic Scheduling Classification of deterministic scheduling problems.

Preprints

``The Mixed Task Scheduling Problem in Open Computing Systems,'' is the title of my presentation at the Second Annual Workshop on Computer Science and Engineering Program, held at the Computer Science Department, Texas A&M University, College Station, TX 77843-3112, on April 8, 1999. In this presentation we focus on the Mixed-Task Scheduling Problem where we explain the basic steps of our solution methodology. We propose a novel framework for Dynamic Management of Idle Processor Capacity in processor schedules. We perform static, off-line analysis and schedule generation for the hard periodic tasks of the given task set. We derive the Released and Serviced workload processes of time, V_i(t), W_i(t), respectively, for i = 1, 2, ..., n. We define the idle processor capacity Z_i(t) as, Z_i(t) := t - W_i(t).
A key ingredient to our algorithms is the efficent, dynamic, run-time derivation of W_i(t). A host of hard non-periodic, sporadic and soft real-time scheduling algorithms can be derived from the W_i(t) processes. We are currently implementing the scheduling algorithms in Open POSIX compliant systems, such as, Sun Solaris 2.7, SGI IRIX 6.5, and HP UX 11.00.

``Development of Portable Middleware Services in POSIX Environments,''appears in the Proceedings of IEEE Workshop on Middleware for Distributed Real-Time Systems and Services, held in conjunction with the IEEE Real-Time Systems Symposium, December 1997. The conference presentation slides can be found here.
This study is a first cut evaluation of the Real-Time service quality of different POSIX implementations, and their suitability for the development of portable middleware. The full version of the paper can be accessed as technical report TAMU-CS-97-012. An earlier technical report TAMU-CS-97-004 presents a preliminary evaluation of the Real-Time service quality of POSIX on Sun Solaris 2.5 and SGI IRIX 6.2.

``An Efficient Steepest-Edge Simplex Algorithm for SIMD Computers,'' appears in the Proc. of The International Conference on Supercomputing, Philadelphia, PA, May 1996. These are the slides of the presentation at the same conference.
This is the technical report TAMU-CS-96-32 of the paper.

``Performance Evaluation of Multistage Interconnection Networks under Uniform and Bursty Traffic,'' discusses the performance of Banyan type, Multi-stage Interconnection Networks (MINs), for multiprocessors and High-Speed Networks. Simulation results are presented for Uniform and Bursty traffic models, based on the Interrupted Bernoulli Process.

``Design and Implementation of the FFT Algorithm on HyperCube MIMD Supercomputers,'' presents the design of FFT algorithms for HyperCube MIMD supercomputers and their performance on a 64 processor, nCube-2 machine.

``The Busy Period of the GI/M/1 Queuing System,'' is a brief overview of classical solution methods for the derivation of the busy period distribution of GI/M/1 queuing systems.

``Implementation and Evaluation of Primal and Dual Simplex Methods under Different Pivot-Selection Techniques in the LPBench Environment,'' on the evaluation of Pivot-Selection methods for Primal and Dual Simplex Algorithms for Linear Programming optimization problems.

``Design of Pipelined Micro-Architectures for Micro-Processors,'' discusses the design of a pipelined micro-architecture for a simple microprocessor.

`` An Advanced Real-Time Ramp Metering System (ARMS),'' (with Liu, S., Lee, G., Chen, Y., Hao, Y., Kim, T.), Texas Department of Transportation, Research Report 1232-24, Austin, Texas, Sep. 1994. This is concerned with the design of real-time ramp metering and control information systems for freeways and urban highways.

Hard copy available. ``Ramp Adaptive Metering Bottleneck Optimization (RAMBO) User's Manual,'' (with Messer, C., Charara, H. and Urbanik, T.), Texas Department of Transportation, Research Report 1232-31, Austin, Texas, Dec. 1994.

Research Projects

DS/DSH
DS/DSH is an infrastructure supporting distributed scheduling and load sharing of POSIX, multi-threaded applications in workstation and server clusters.
Currently, the system provides the following services: (i) dynamic state probing of local host, (ii) dynamic state dissemination to hosts participating in the NOW, (iii) continuous network probing among hosts for communications latency, (iv) process level load distribution, (v) automatic sensing of static host capabilities, (e.g., processor capacity, speed, number, memory size, host-to-host communication latency and bandwidth etc.).
The architecture leverages basic POSIX and SVr4 capabilities, including, multi-threading management / scheduling / IPC, signals (Pthreads), SYSVr4/POSIX process level control, TCP/IP protocol communication (TCP/UDP sockets, IP-multicasting, etc. ), shared memory intra-host communication. Currently, research prototypes are under development on Sun Solaris 2.5, 2,6, SGI IRIX 6.2, 6.5, and other platforms with POSIX support (e.g., HP-UX 11.00 on HP 9000/800, etc.)
Current work investigates the effectiveness of mechanisms for user-level management of threads and processes, within the same and remote nodes. Innovative scheduling algorithms for time sensitive/constraint applications are being developed and they are going to be incorporated into the architecture for evaluation.

POSIX
Evaluation
POSIX is a robust, function reach specification for portable operating system software. Most current UNIX systems are building Pthread support on top of SVr4 kernel mechanisms. Modern applications with timing constraints will soon demand kernel infrastructure that is ``cognizant'' of their timing semantics. POSIX provides direct, albeit primitive, support for periodic, hard real time applications, and one can build ``a'' periodic service using timers, SIGnals, etc., even on systems without the POSIX functions. However, there is no capacity management mechanisms, beyond the well known ``degrading priority'' Time-Sharing, or the fixed-priority (FIFO or Round-Robin) dispatching. Worse yet, most applications consist of components with mixed types of timing constraints and criticalities. For instance, admission control and management of aperiodic/sporadic task is non-existent, as is the capacity management for memory and network I/O. The application needs to fill-in the gaps by providing all this functionality at the user-level. A tighter cooperation of user application and kernel in the scheduling and resource allocation decisions is necessary.
Kernel timer resolution along with the overhead of the various mechanisms of the systems dispatcher, place absolute limits on the types and time resolution of the schedulable events in the system. These limits become more restrictive to user-level thread and process schedulers. For instance, an application requiring to exert fine granularity control to the way communications packet/cell processing is scheduled, is restricted by the timer resolution exported by the kernel and by the several other kernel mechanisms (e.g., STREAMS) over which has no control.
We are evaluating statistically the quality of service that current POSIX implementations can deliver to applications with Quality of Service requirements. We are evaluating system calls for multi-threading management, timer services, synchronization and the behavior of the kernel and thread schedulers. We are focusing on the overhead, stability and scalability of the corresponding kernel and thread mechanisms. The results are used as a guide for the development of more powerful mechanisms that applications can use to exercise tight control over their pthread/process scheduling and the allocation of the systems resources.

AtmSim
ATM Network
Simulation
AtmSim is a simulation package for entire ATM networks. The simulator is of the discrete event, discrete time type, simulating the network behavior at three levels: (i) the Virtual Path Connection, (ii) the message, and (iii) the cell levels.
It can be used as a workbench for the development and evaluation of (i) rate-based or credit-based flow-control strategies, and (ii) cell scheduling strategies at the border or network switches. The entire ATM network is defined by the static resource specification that includes, a specification of the various switches, input, output ports, buffer sizes, CLP, leaky bucket policies, and physical link bandwidths, propagation delays and connectivity to switches and user end-points. Currently the simulator supports two types of border (user) switches and one type of network ATM switch. All are of the output-buffered, non-blocking switch fabric type.
The user switches have leaky-bucket per VPC. The input traffic can be obtained by two sources: supplied by a file or socket or statistically generated by the traffic module of the simulator. We can use traffic source from file or socket to supply communication traces from actual connections, in the form of (TS_i,j, i, s_i,j), where, TS_i,j is the arrival timestamp of the j-th message from VPC i, with size s_i,j. The generated traffic sources are of the Interrupted-Bernoulli Process (IBP) or ON-OFF type. ON and OFF periods follow the Geometric distribution with given parameters. VPC_i is determined by the IBP parameters: (p_i, q_i, a_i), where:

p_i:=P{X_n+1 =1|X_n=1},

q_i:=P{X_n+1 =0|X_n=0}, and

a_i:=P{``there is a cell arrival at t_n'' | X_n=1}

Currently, statistical results (average throughput, latency and variance, cell loss probability) are generated for each VPC at the message and cell levels. Statistical results are generated also for each one of the buffers of every switch (average buffer occupancy, variance, buffer overflow probability).
The system can be expanded by adding new switch types (e.g.,blocking type) and by introducing new flow-control and scheduling algorithms. The simulator can be parallelized to run on shared-memory multiprocessors. There is an old draft report describing an initial stage of AtmSim.
Index Terms:ATM Networks, VPC, Discrete Time - Discrete State Simulation, Bursty Traffic Sources, Leaky Bucket, Interrupted Bernoulli Process, Output-Buffered ATM Switches.

Joint Scheduling
Algorithms
Modern applications place challenging requirements on the underlying Operating System (OS). They consist of several components, each with different timing constraints and resource usage requirements. Current OS, exemplified by the various System V release 4 (SVr4) UNIX flavors, provide support for a generic ``Time-Sharing'' (TS) process class and a very rudimentary ``Real-Time'' (RT) class. The RT class is usually not accessible by regular user processes and it only provides a Fixed Priority dispatching mechanism. Resource allocation, admission control and scheduling policies and mechanisms are absent. The missing functionality has to be provided by ad-hoc user-level infrastructure, that is platform dependent. We investigate ``Joint Task Scheduling'' algorithms that can provide the timing and resource usage guarantees to applications.
We are interested in applications that consist of different components which can be (i) periodic, (ii) sporadic, (iii) aperiodic, and (iv) interactive with proportional fairness requirements. A periodic task iis defined by the quadruple (T_i, C_i, r_i, D_i), where T_i is a fixed request period, C_i is the worst case execution time, r_i is the initial release time, and D_i is a relative deadline by which the task has to finish. Sporadic and aperiodic tasks jare defined by triples, (r_j, C_j, D_j), where r_j is its release time, C_j is its computation requirements, and D_j is its relative deadline. A sporadic task has hard deadline, meaning that, if a deadline is missed the system will suffer catastrophic consequences. An aperiodic task has soft-deadline, which means that the utility the system derives from executing it diminishes with the task's lateness. The system attempts to execute aperiodic tasks as early as possible, and minimize their lateness. An interactive task requires response times compatible with the human activity that the task serves (e.g., typing text, viewing graphics, etc.,). Interactive tasks have no concretely prescribed requirements, except from receiving a fair portion of the system resources. Interactive tasks are covered adequately by the present OS schedulers, which are usually based on the decaying priority dispatch rule of the SVr4 system.
The real-time periodic scheduling problem has been studied extensively in the literature. However, the joint scheduling of mixtures of periodic and non-periodic tasks remains a challenging problem. Several approaches have been proposed, based pre-dominately on either fixed-priority (FPS) or dynamic priority (DPS) scheduling schemes. FPS schemes include the polling, deferred, priority-exchange and sporadic servers. Previous work has shown experimentally that each one of these servers performs better than its predecessor in the aforementioned order. However, there are cases where arriving non-periodic tasks have to be rejected by the system, although there is sufficient processor capacity to guarantee their successful completion before their deadlines. The reason for this is that these algorithms attempt to offer a fair opportunity to non-periodic tasks to use the processor, by competing in restricted ways with the regular periodic tasks. They are not, however, designed to recover the entire available processor capacity in a schedule. We can say that FPS schemes are biased towards periodic real-time tasks, at the expense of all other task types. However, mixed workloads pose widely varying timing requirements which are, in many cases, not effectively mapped into fixed-priorities, request periods and worst case execution times. DPS schemes include the classic earliest-due-date-first (EDD or EDF), the least-laxity-first (LLF), and several deadline-driven versions of the FPS server schemes. The disadvantage of DPS techniques is that they basically schedule the non-periodic tasks on a best-effort basis. Each scheduling decision usually requires time T(n) = O(logn), where n is the number of ready tasks in the system. Another disadvantage is that, there is no universally good method to map the resource requirements of tasks which are interactive or have soft real-time timing constraints, into deadlines.
Our approach focuses on the management of the idle processor capacity which is left after the periodic tasks of the schedule have been processed. The basic objective of non-periodic scheduling is to make decisions concerning the schedulability of dynamically arriving sporadic and/or aperiodic tasks. The algorithm has to decide, first, if there is sufficient processor idle (i.e., left-over) capacity, and, secondly, determine when the newly arrived task will execute, if admitted. The slack-stealing approach has been proposed as a method to recover and utilize the idle processor capacity. However, currently existing slack-stealing algorithms suffer from inordinately high overhead for computation or storage, and inaccurate estimation of the slack. The excessive computation overhead of current approaches is detrimental to the performance of the system, as the scheduler in order to make the decisions consumes valuable idle processor capacity, excessively. We can show that the direct determination of available slack within a time interval [t, t+h] exactly, takes exponential time T(n) = O(2ⁿ), and it is not, thus, suitable for a run time dynamic implementation. We propose a method that makes exact slack pre-computation possible, at system design time. At first, we derive several key properties for the schedules of RT periodic tasks based on two model fixed priority, preemptive scheduling methods, called FPF and LDL. We derive their schedules S(t), with the associated released workload V_i(t) processed workload W_i(t), and the idle processor capacity Z_i(t) processes that characterize them. This approach leads to extremely efficient decision making for the admission of dynamically arriving tasks. The disadvantage of this approach is that storage requirements may become excessive. We propose to alleviate this problem in three different ways. (i) We precompute only certain key portions of the available slack off-line, and at the task admission time we perform a minimal computation which allows us to decide directly and exactly, if there is sufficient available processor capacity to guarantee the dynamic task. (ii)We compute the idle processor capacity dynamically, and continuously, and (ii) we generate dynamically the schedule, when a new non-periodic task requests admission. These three approaches represent different trade-off points between storage space and computation time. The advantage of our approach is that, we offer a system model that captures concisely and measures exactly the idle processor capacity (Z_i(t) and the other auxiliary quantities), as a processes of time. We offer solutions to the sporadic task scheduling problem based on idle processor capacity management. We present concrete and realistic solutions, with very efficient run-time implementation in terms of computation time, especially when compared to currently existing slack-stealing methods. We present a spectrum of possible implementations that trade-off space for time, so that a suitable design point can be implemented on actual systems. We are currently experimenting with actual system implementation in order to obtain accurate measurements of realistic timing overhead.
In the next stage we plan to include in our joint-task scheduling framework, support for proportionally fair scheduling of interactive tasks. It is needless to say that the current scheduling methodologies are being implemented within the open POSIX framework for multi-threaded computation. Favorable results on a single node implementation will give the green light for a distributed system deployment on the DS/DSH infrastructure, we mentioned above, (and maybe, within the AtmSim ATM network simulator).
Index Terms:Fixed Priority Preemptive Scheduling; Periodic, Sporadic, Aperiodic Scheduling; Hard Real-Time Tasks; Idle-Capacity Management; FPF/LDL Schedules, Task Relocation.

Parallel
Processing
This research study proposes an efficient parallelization of the Primal and Dual Simplex algorithms for Linear Programming (LP) problems on Single-Instruction Multiple-Data (SIMD) computers, interconnected by toroidal-mesh networks. The algorithms are based on the Steepest-Edge pivot selection method and the tableau representation of the constraint matrix. The initial canonical tableau is formed, partitioned into a grid of sub-matrices and distributed to the individual Processor Element (PE) memories. At the same time, the reduced cost row and the basic feasible solution column are partially replicated on each one of the PEs. The Steepest-Edge method performs a sequence of global reduction operations, utilizing information from local replicas, in order to select the next pivot element. The pivot row and column are efficiently multicasted to PEs before pivot computation steps, by utilizing the geometry and pipelining properties of the interconnect. The proposed parallelization has optimal asymptotic speedup and scalability properties, and performance comparisons show that as LP problem sizes increase the speed-ups obtained by MasPar's MP-1 and MP-2 models are in the order of 100 times, and 1,000 times, respectively, over sequential versions of the Steepest-Edge Simplex algorithm running on high-end Unix workstations.
Index Terms:Single-Instruction Multiple-Data (SIMD), Steepest-Edge Pivot Selection, Simplex, Matrix Partitioning, Data Replication, Global Reductions, Toroidal-Mesh Networks, Pipelined Networks.

Work

DataLink
Laboratory
The DataLink Research Laboratory page (for `RTDS' group members only). I have been one of the main contributors of the analysis, design, and development of the infrastructure of the Lab. The software infrastructure is a ``three-tiered'' system. An ORACLE relational database (version 7, production) is the storage back-end of the data repository. HTTP servers are the middle tier, playing the rele of resource and data brokers, providing access over the global Internet. Several C-embedded-SQL modules provide client access to the data repository, by dynamically forming SQL queries from interactive WEB pages, which are sent to the ORACLE SQL engine. The embedded-SQL modules finally receive the results and transform them into WEB pages, by generating dynamic HTTP mark-up language. The pages are finally delivered to client browsers via the HTTP servers.
The entire system resides on 4 SUN Ultra-Sparc, UNIX workstations, with ample memory (~1,088 MBytes combined) and on-line disk capacity (~52 GBytes). The ORACLE server engine runs on one UNIX workstation and two HTTP servers run on two other UNIX hosts. The database currently stores in excess of 78,000,000 entries. Specialized C-embedded-SQL programs perform queries, and extraction of several statistical measures on the database contents. Graphical output can be generated and rendered in the popular PostScript and PDF formats. Our current approach logically compresses the hefty 150MBytes of data that the sources capture every day, into relational table rows that require a mere 5.9MBytes. A host of auxiliary modules execute nightly in the background to bring the new data in and update the database. The systems operation is monitored and maintained daily. Click here for a snapshot of the data. (Note that, some portions of this snapshot page are intentionally not working due to authorization restrictions, and the snapshot itself is static).

TransLink
Laboratory
The TransLink Research Laboratory page, is the initial laboratory WEB page. Click here for a snapshot of the first version of the data in this Lab's database. (This snapshot is also static for authorization restriction reasons.)

Bye

Go back to Computer Science home page.
Visit the home page of the Hellenic Student Association (HSA) at the Texas A&M University.
Visit the Texas A&M University home page.
$Id: index.html,v 1.11 1999/04/18 10:45:50 miket Exp miket $

Research Projects
DS/DSH	DS/DSH is an infrastructure supporting distributed scheduling and load sharing of POSIX, multi-threaded applications in workstation and server clusters. Currently, the system provides the following services: (i) dynamic state probing of local host, (ii) dynamic state dissemination to hosts participating in the NOW, (iii) continuous network probing among hosts for communications latency, (iv) process level load distribution, (v) automatic sensing of static host capabilities, (e.g., processor capacity, speed, number, memory size, host-to-host communication latency and bandwidth etc.). The architecture leverages basic POSIX and SVr4 capabilities, including, multi-threading management / scheduling / IPC, signals (Pthreads), SYSVr4/POSIX process level control, TCP/IP protocol communication (TCP/UDP sockets, IP-multicasting, etc. ), shared memory intra-host communication. Currently, research prototypes are under development on Sun Solaris 2.5, 2,6, SGI IRIX 6.2, 6.5, and other platforms with POSIX support (e.g., HP-UX 11.00 on HP 9000/800, etc.) Current work investigates the effectiveness of mechanisms for user-level management of threads and processes, within the same and remote nodes. Innovative scheduling algorithms for time sensitive/constraint applications are being developed and they are going to be incorporated into the architecture for evaluation.
POSIX Evaluation	POSIX is a robust, function reach specification for portable operating system software. Most current UNIX systems are building Pthread support on top of SVr4 kernel mechanisms. Modern applications with timing constraints will soon demand kernel infrastructure that is ``cognizant'' of their timing semantics. POSIX provides direct, albeit primitive, support for periodic, hard real time applications, and one can build ``a'' periodic service using timers, SIGnals, etc., even on systems without the POSIX functions. However, there is no capacity management mechanisms, beyond the well known ``degrading priority'' Time-Sharing, or the fixed-priority (FIFO or Round-Robin) dispatching. Worse yet, most applications consist of components with mixed types of timing constraints and criticalities. For instance, admission control and management of aperiodic/sporadic task is non-existent, as is the capacity management for memory and network I/O. The application needs to fill-in the gaps by providing all this functionality at the user-level. A tighter cooperation of user application and kernel in the scheduling and resource allocation decisions is necessary. Kernel timer resolution along with the overhead of the various mechanisms of the systems dispatcher, place absolute limits on the types and time resolution of the schedulable events in the system. These limits become more restrictive to user-level thread and process schedulers. For instance, an application requiring to exert fine granularity control to the way communications packet/cell processing is scheduled, is restricted by the timer resolution exported by the kernel and by the several other kernel mechanisms (e.g., STREAMS) over which has no control. We are evaluating statistically the quality of service that current POSIX implementations can deliver to applications with Quality of Service requirements. We are evaluating system calls for multi-threading management, timer services, synchronization and the behavior of the kernel and thread schedulers. We are focusing on the overhead, stability and scalability of the corresponding kernel and thread mechanisms. The results are used as a guide for the development of more powerful mechanisms that applications can use to exercise tight control over their pthread/process scheduling and the allocation of the systems resources.
AtmSim ATM Network Simulation	AtmSim is a simulation package for entire ATM networks. The simulator is of the discrete event, discrete time type, simulating the network behavior at three levels: (i) the Virtual Path Connection, (ii) the message, and (iii) the cell levels. It can be used as a workbench for the development and evaluation of (i) rate-based or credit-based flow-control strategies, and (ii) cell scheduling strategies at the border or network switches. The entire ATM network is defined by the static resource specification that includes, a specification of the various switches, input, output ports, buffer sizes, CLP, leaky bucket policies, and physical link bandwidths, propagation delays and connectivity to switches and user end-points. Currently the simulator supports two types of border (user) switches and one type of network ATM switch. All are of the output-buffered, non-blocking switch fabric type. The user switches have leaky-bucket per VPC. The input traffic can be obtained by two sources: supplied by a file or socket or statistically generated by the traffic module of the simulator. We can use traffic source from file or socket to supply communication traces from actual connections, in the form of (TS_i,j, i, s_i,j), where, TS_i,j is the arrival timestamp of the j-th message from VPC i, with size s_i,j. The generated traffic sources are of the Interrupted-Bernoulli Process (IBP) or ON-OFF type. ON and OFF periods follow the Geometric distribution with given parameters. VPC_i is determined by the IBP parameters: (p_i, q_i, a_i), where: p_i:=P{X_n+1 =1\|X_n=1}, q_i:=P{X_n+1 =0\|X_n=0}, and a_i:=P{``there is a cell arrival at t_n'' \| X_n=1} Currently, statistical results (average throughput, latency and variance, cell loss probability) are generated for each VPC at the message and cell levels. Statistical results are generated also for each one of the buffers of every switch (average buffer occupancy, variance, buffer overflow probability). The system can be expanded by adding new switch types (e.g.,blocking type) and by introducing new flow-control and scheduling algorithms. The simulator can be parallelized to run on shared-memory multiprocessors. There is an old draft report describing an initial stage of AtmSim. Index Terms:ATM Networks, VPC, Discrete Time - Discrete State Simulation, Bursty Traffic Sources, Leaky Bucket, Interrupted Bernoulli Process, Output-Buffered ATM Switches.
Joint Scheduling Algorithms	Modern applications place challenging requirements on the underlying Operating System (OS). They consist of several components, each with different timing constraints and resource usage requirements. Current OS, exemplified by the various System V release 4 (SVr4) UNIX flavors, provide support for a generic ``Time-Sharing'' (TS) process class and a very rudimentary ``Real-Time'' (RT) class. The RT class is usually not accessible by regular user processes and it only provides a Fixed Priority dispatching mechanism. Resource allocation, admission control and scheduling policies and mechanisms are absent. The missing functionality has to be provided by ad-hoc user-level infrastructure, that is platform dependent. We investigate ``Joint Task Scheduling'' algorithms that can provide the timing and resource usage guarantees to applications. We are interested in applications that consist of different components which can be (i) periodic, (ii) sporadic, (iii) aperiodic, and (iv) interactive with proportional fairness requirements. A periodic task iis defined by the quadruple (T_i, C_i, r_i, D_i), where T_i is a fixed request period, C_i is the worst case execution time, r_i is the initial release time, and D_i is a relative deadline by which the task has to finish. Sporadic and aperiodic tasks jare defined by triples, (r_j, C_j, D_j), where r_j is its release time, C_j is its computation requirements, and D_j is its relative deadline. A sporadic task has hard deadline, meaning that, if a deadline is missed the system will suffer catastrophic consequences. An aperiodic task has soft-deadline, which means that the utility the system derives from executing it diminishes with the task's lateness. The system attempts to execute aperiodic tasks as early as possible, and minimize their lateness. An interactive task requires response times compatible with the human activity that the task serves (e.g., typing text, viewing graphics, etc.,). Interactive tasks have no concretely prescribed requirements, except from receiving a fair portion of the system resources. Interactive tasks are covered adequately by the present OS schedulers, which are usually based on the decaying priority dispatch rule of the SVr4 system. The real-time periodic scheduling problem has been studied extensively in the literature. However, the joint scheduling of mixtures of periodic and non-periodic tasks remains a challenging problem. Several approaches have been proposed, based pre-dominately on either fixed-priority (FPS) or dynamic priority (DPS) scheduling schemes. FPS schemes include the polling, deferred, priority-exchange and sporadic servers. Previous work has shown experimentally that each one of these servers performs better than its predecessor in the aforementioned order. However, there are cases where arriving non-periodic tasks have to be rejected by the system, although there is sufficient processor capacity to guarantee their successful completion before their deadlines. The reason for this is that these algorithms attempt to offer a fair opportunity to non-periodic tasks to use the processor, by competing in restricted ways with the regular periodic tasks. They are not, however, designed to recover the entire available processor capacity in a schedule. We can say that FPS schemes are biased towards periodic real-time tasks, at the expense of all other task types. However, mixed workloads pose widely varying timing requirements which are, in many cases, not effectively mapped into fixed-priorities, request periods and worst case execution times. DPS schemes include the classic earliest-due-date-first (EDD or EDF), the least-laxity-first (LLF), and several deadline-driven versions of the FPS server schemes. The disadvantage of DPS techniques is that they basically schedule the non-periodic tasks on a best-effort basis. Each scheduling decision usually requires time T(n) = O(logn), where n is the number of ready tasks in the system. Another disadvantage is that, there is no universally good method to map the resource requirements of tasks which are interactive or have soft real-time timing constraints, into deadlines. Our approach focuses on the management of the idle processor capacity which is left after the periodic tasks of the schedule have been processed. The basic objective of non-periodic scheduling is to make decisions concerning the schedulability of dynamically arriving sporadic and/or aperiodic tasks. The algorithm has to decide, first, if there is sufficient processor idle (i.e., left-over) capacity, and, secondly, determine when the newly arrived task will execute, if admitted. The slack-stealing approach has been proposed as a method to recover and utilize the idle processor capacity. However, currently existing slack-stealing algorithms suffer from inordinately high overhead for computation or storage, and inaccurate estimation of the slack. The excessive computation overhead of current approaches is detrimental to the performance of the system, as the scheduler in order to make the decisions consumes valuable idle processor capacity, excessively. We can show that the direct determination of available slack within a time interval [t, t+h] exactly, takes exponential time T(n) = O(2ⁿ), and it is not, thus, suitable for a run time dynamic implementation. We propose a method that makes exact slack pre-computation possible, at system design time. At first, we derive several key properties for the schedules of RT periodic tasks based on two model fixed priority, preemptive scheduling methods, called FPF and LDL. We derive their schedules S(t), with the associated released workload V_i(t) processed workload W_i(t), and the idle processor capacity Z_i(t) processes that characterize them. This approach leads to extremely efficient decision making for the admission of dynamically arriving tasks. The disadvantage of this approach is that storage requirements may become excessive. We propose to alleviate this problem in three different ways. (i) We precompute only certain key portions of the available slack off-line, and at the task admission time we perform a minimal computation which allows us to decide directly and exactly, if there is sufficient available processor capacity to guarantee the dynamic task. (ii)We compute the idle processor capacity dynamically, and continuously, and (ii) we generate dynamically the schedule, when a new non-periodic task requests admission. These three approaches represent different trade-off points between storage space and computation time. The advantage of our approach is that, we offer a system model that captures concisely and measures exactly the idle processor capacity (Z_i(t) and the other auxiliary quantities), as a processes of time. We offer solutions to the sporadic task scheduling problem based on idle processor capacity management. We present concrete and realistic solutions, with very efficient run-time implementation in terms of computation time, especially when compared to currently existing slack-stealing methods. We present a spectrum of possible implementations that trade-off space for time, so that a suitable design point can be implemented on actual systems. We are currently experimenting with actual system implementation in order to obtain accurate measurements of realistic timing overhead. In the next stage we plan to include in our joint-task scheduling framework, support for proportionally fair scheduling of interactive tasks. It is needless to say that the current scheduling methodologies are being implemented within the open POSIX framework for multi-threaded computation. Favorable results on a single node implementation will give the green light for a distributed system deployment on the DS/DSH infrastructure, we mentioned above, (and maybe, within the AtmSim ATM network simulator). Index Terms:Fixed Priority Preemptive Scheduling; Periodic, Sporadic, Aperiodic Scheduling; Hard Real-Time Tasks; Idle-Capacity Management; FPF/LDL Schedules, Task Relocation.
Parallel Processing	This research study proposes an efficient parallelization of the Primal and Dual Simplex algorithms for Linear Programming (LP) problems on Single-Instruction Multiple-Data (SIMD) computers, interconnected by toroidal-mesh networks. The algorithms are based on the Steepest-Edge pivot selection method and the tableau representation of the constraint matrix. The initial canonical tableau is formed, partitioned into a grid of sub-matrices and distributed to the individual Processor Element (PE) memories. At the same time, the reduced cost row and the basic feasible solution column are partially replicated on each one of the PEs. The Steepest-Edge method performs a sequence of global reduction operations, utilizing information from local replicas, in order to select the next pivot element. The pivot row and column are efficiently multicasted to PEs before pivot computation steps, by utilizing the geometry and pipelining properties of the interconnect. The proposed parallelization has optimal asymptotic speedup and scalability properties, and performance comparisons show that as LP problem sizes increase the speed-ups obtained by MasPar's MP-1 and MP-2 models are in the order of 100 times, and 1,000 times, respectively, over sequential versions of the Steepest-Edge Simplex algorithm running on high-end Unix workstations. Index Terms:Single-Instruction Multiple-Data (SIMD), Steepest-Edge Pivot Selection, Simplex, Matrix Partitioning, Data Replication, Global Reductions, Toroidal-Mesh Networks, Pipelined Networks.

Hi
	Take a look at the ``official'' information concerning modern Greece. There are some unofficial data, though, you may also like to study. See for instance, Greek Coasts, gogreece, webcom, Ellada, etc. There is plenty of useful information about my country and thousands of pictures worth viewing (for the day-dreaming travelers). So enjoy your journeys! Visit this excellent site, if you are interested in the prehistoric and classic Greece and its accomplishments. You can follow this link for an extensive collection of resources on Greece, from antiquity to modern days. In this site you can find information related to greek cultural history. In this site you can find several intriguing and little-known facts about Greece, its language and the journeys of Greeks through time and the big seas. Here are a few photos from some (relatively) recent activities of the Hellenic Student Association at the Texas A&M University.

Resume
	ASCII Text Resume
Research Interests
Operating Systems	Interesting information on existing research and commercial Operating Systems. Open UNIX standard Single-UNIX Specification v2 (UNIX 98). Collection of papers at the OSF.
Multi-Threaded Computation	Bibliography on threads and multithreading. Although somewhat dated, it is still a good starting point for articles on threads.
Deterministic and Stochastic Scheduling	Classification of deterministic scheduling problems.
Preprints
	``The Mixed Task Scheduling Problem in Open Computing Systems,'' is the title of my presentation at the Second Annual Workshop on Computer Science and Engineering Program, held at the Computer Science Department, Texas A&M University, College Station, TX 77843-3112, on April 8, 1999. In this presentation we focus on the Mixed-Task Scheduling Problem where we explain the basic steps of our solution methodology. We propose a novel framework for Dynamic Management of Idle Processor Capacity in processor schedules. We perform static, off-line analysis and schedule generation for the hard periodic tasks of the given task set. We derive the Released and Serviced workload processes of time, V_i(t), W_i(t), respectively, for i = 1, 2, ..., n. We define the idle processor capacity Z_i(t) as, Z_i(t) := t - W_i(t). A key ingredient to our algorithms is the efficent, dynamic, run-time derivation of W_i(t). A host of hard non-periodic, sporadic and soft real-time scheduling algorithms can be derived from the W_i(t) processes. We are currently implementing the scheduling algorithms in Open POSIX compliant systems, such as, Sun Solaris 2.7, SGI IRIX 6.5, and HP UX 11.00.
	``Development of Portable Middleware Services in POSIX Environments,''appears in the Proceedings of IEEE Workshop on Middleware for Distributed Real-Time Systems and Services, held in conjunction with the IEEE Real-Time Systems Symposium, December 1997. The conference presentation slides can be found here. This study is a first cut evaluation of the Real-Time service quality of different POSIX implementations, and their suitability for the development of portable middleware. The full version of the paper can be accessed as technical report TAMU-CS-97-012. An earlier technical report TAMU-CS-97-004 presents a preliminary evaluation of the Real-Time service quality of POSIX on Sun Solaris 2.5 and SGI IRIX 6.2.
	``An Efficient Steepest-Edge Simplex Algorithm for SIMD Computers,'' appears in the Proc. of The International Conference on Supercomputing, Philadelphia, PA, May 1996. These are the slides of the presentation at the same conference. This is the technical report TAMU-CS-96-32 of the paper.
	``Performance Evaluation of Multistage Interconnection Networks under Uniform and Bursty Traffic,'' discusses the performance of Banyan type, Multi-stage Interconnection Networks (MINs), for multiprocessors and High-Speed Networks. Simulation results are presented for Uniform and Bursty traffic models, based on the Interrupted Bernoulli Process.
	``Design and Implementation of the FFT Algorithm on HyperCube MIMD Supercomputers,'' presents the design of FFT algorithms for HyperCube MIMD supercomputers and their performance on a 64 processor, nCube-2 machine.
	``The Busy Period of the GI/M/1 Queuing System,'' is a brief overview of classical solution methods for the derivation of the busy period distribution of GI/M/1 queuing systems.
	``Implementation and Evaluation of Primal and Dual Simplex Methods under Different Pivot-Selection Techniques in the LPBench Environment,'' on the evaluation of Pivot-Selection methods for Primal and Dual Simplex Algorithms for Linear Programming optimization problems.
	``Design of Pipelined Micro-Architectures for Micro-Processors,'' discusses the design of a pipelined micro-architecture for a simple microprocessor.
	`` An Advanced Real-Time Ramp Metering System (ARMS),'' (with Liu, S., Lee, G., Chen, Y., Hao, Y., Kim, T.), Texas Department of Transportation, Research Report 1232-24, Austin, Texas, Sep. 1994. This is concerned with the design of real-time ramp metering and control information systems for freeways and urban highways.
Hard copy available.	``Ramp Adaptive Metering Bottleneck Optimization (RAMBO) User's Manual,'' (with Messer, C., Charara, H. and Urbanik, T.), Texas Department of Transportation, Research Report 1232-31, Austin, Texas, Dec. 1994.