Software DSMs (SDSMs) are an appealing alternative to message passing, since they facilitate the programmability of clusters. However the ease of programming comes at the expense of performance. Although accesses of data that reside to the memory of remote nodes are transparent to the programmer, they suffer from significantly higher latencies compared to local accesses. As a consequence, it is desirable to move data as close as possible to the nodes that need them most. In this paper we introduce a protocol for dynamically migrating memory pages in home-based SDSM systems. In these systems each page has a designated home node; yet our protocol allows a node that heavily modifies a page to become its new home. The new protocol targets multiple-writer DSMs, i.e. DSMs that allow multiple nodes to concurrently modify the same page. The process is dynamic and transparent to the applications programmer. Moreover, it does not assume a specific consistency protocol. Experimental results show that our page migration protocol reduces remote page modifications, decreases the average memory access latency, as well as the overhead for the preservation of memory consistency. The benefit for the end-user is a significant improvement in application performance

Dynamic page migration, when employed in distributed shared memory (DSM) systems offers several advantages: (i) reduces the latency of memory accesses, (ii) improves resource utilization by considering the computational and communicational needs of the applications and adapting to the changing resource availability, and (iii) achieves the above with lower overhead than traditional approaches that rely on thread migration. We propose a simple and efficient page migration mechanism that dynamically allocates shared memory pages to home nodes. Each page has a designated home node and nodes that heavily modify the pages can become their new homes. In our protocol, to avoid redundant page transfers, we perform migration only when the number of modifications of a page becomes larger than a threshold. The migration information is piggybacked on the existing synchronization messages to minimize the communication overhead. The migration decision is taken locally, at the home of each page. We have implemented our mechanism in the JIAJIA software DSM. Performance evaluation using real application benchmarks shows that our mechanism significantly reduces remote page modifications, improves memory access latencies, and achieves better performance than its competitors. We observe that the cost of executing the algorithm and of migrating the pages is amortized by the benefits gained.

The bus that connects processors to memory is known to be a major architectural bottleneck in SMPs. However, both software and scheduling policies for these systems generally focus on memory hierarchy optimizations and do not address the bus bandwidth limitations directly. We first present experimental results which indicate that bus saturation can cause an up to almost three-fold slowdown to applications. Motivated by these results, we introduce two scheduling policies that take into account the bus bandwidth consumption of applications. The necessary information is provided by performance monitoring counters which are present in all modern processors. Our algorithms organize jobs so that processes with high-bandwidth and low-bandwidth demands are co-scheduled to improve bus bandwidth utilization without saturating the bus. We found that our scheduler is effective with applications of varying bandwidth requirements, from very low to close to the limit of saturation. We also tuned our scheduler for robustness in the presence of bursts of high bus bandwidth consumption from individual jobs. The new scheduling policies improve system throughput by up to 68% (26% in average) in comparison with the standard Linux scheduler

The authors introduce a generic and flexible ontology for modeling ill-structured knowledge domains within intelligent educational systems. The ontology is based on the theory of cognitive flexibility. We have prototyped the ontology on a deductive object oriented database system. We provide simple and concrete examples that demonstrate benefits of the ontology, such as extensibility, flexibility and support for implementing authoring environments.

The paper addresses the implementation of a watermarking environment and of a metadata database system of digital images for the protection and management of the intellectual property rights of digitized material of the Hellenic cultural heritage. The work has been conducted as part of the Praxitelis Project, which was presented during the Culture Track of the WWW9 Conference in Amsterdam. This project is focusing on managing digital surrogates of high-quality photographs of artifacts, monuments and sites and on countering electronic "theft" of online digital material. The design and implementation of the project is under development by the High Performance Information Systems Laboratory (HPCLAB) of the department of Computer Engineering and Informatics of the University of Patras, Greece. The system is specifically applied to cultural heritage and the Hellenic Ministry of Culture (HMC) is the main user.

We present novel algorithms for efficient scheduling of synchronizing threads on multiprogrammed SMPs. The algorithms are based on intra-application priority control of synchronizing threads. We refer to such algorithms with the term "informing algorithms". Prerequisite for informing algorithms is the use of an efficient communication medium between the user- and kernel-level and the existence of in-kernel mechanisms that allow the applications to cooperate with the OS scheduler. The applications are given the opportunity to influence, in a non-intrusive manner, the scheduling decisions concerning their threads. We compare the performance of our informing algorithms with the performance of corresponding scheduler-oblivious algorithms under multiprogramming. We experimented on a small-scale, Intel x86-based SMP, running Linux, using both microbenchmarks and applications from the Splash-2 benchmark suite. The results substantiate the superiority of our approach and indicate that the philosophy of informing algorithms may be applicable in a wide range of algorithms and architectures.

This paper explores previously established and novel methods for scaling the performance of OpenMP on NUMA architectures. The spectrum of methods under investigation includes OS-level automatic page placement algorithms, dynamic page migrationd manual data distribution. The trade-off that these methods face lies between performance and programming effort. Automatic page placement algorithms are transparent to the programmer, but may compromise memory access locality. Dynamic page migration is also transparent, but requires careful engineering of online algorithms to be effective. Manual data distribution on the other requires substantial programming effort and architecture-specific extensions to OpenMP, but may localize memory accesses in a nearly optimal manner.

This paper presents algorithms for improving the performance of parallel programs on multiprogrammed shared-memory NUMA multiprocessors, via the use of user-level dynamic page migration. The idea that drives the algorithms is that a page migration engine can perform accurate and timely page migrations in a multiprogrammed system if it can correlate page reference information with scheduling information obtained from the operating system. The necessary page migrations can be performed as a response to scheduling events that break the implicit association between threads and their memory affinity sets. We present two algorithms that use feedback from the kernel scheduler to aggressively migrate pages upon thread migrations. The first algorithm exploits the iterative nature of parallel programs, while the second targets generic codes without making assumptions on their structure. Performance evaluation on an SGI Origin2000 shows that our page migration algorithms provide substantial improvements in throughput of up to 264% compared to the native IRIX 6.5.5 page placement and migration schemes.

This paper presents user-level dynamic page migration, a runtime technique which transparently enables parallel pro-grams to tune their memory performance on distributed shared memory multiprocessors, with feedback obtained from dynamic monitoring of memory activity. Our technique exploits the iterative nature of parallel programs and information available to the program both at compile time and at runtime in order to improve the accuracy and the timeliness of page migrations, as well as amortize better the overhead, compared to page migration engines implemented in the operating system. We present an adaptive page migration algorithm based on a competitive and a predictive criterion. The competitive criterion is used to correct poor page placement decisions of the operating system, while the predictive criterion makes the algorithm respon-sive to scheduling events that necessitate immediate page migrations, such as preemptions and migrations of threads. We also present a new technique for preventing page ping-pong and a mechanism for monitoring the performance of page migration algorithms at runtime and tuning their sen-sitive parameters accordingly. Our experimental evidence on a SGI Origin2000 shows that unmodified OpenMP codes linked with our runtime system for dynamic page migration are effectively immune to the page placement strategy of the operating system and the associated problems with data locality. Furthermore, our runtime system achieves solid performance improvements compared to the IRIX 6.5.5 page migration engine, for single parallel OpenMP codes and multiprogrammed workloads.

This paper presents a new methodology for implementing fast synchronization on scalable cache-coherent multiprocessors, through the use of hybrid primitives. Hybrid primitives leverage commodity hardware to speed-up the execution of the atomic remote Read-Modify-Write (RMW) instructions employed in synchronization algorithms to resolve contending processors, while exploiting the caches to reduce network traffic during the waiting and release phases of a synchronization primitive. We present a systematic methodology for transforming any synchronization primitive that uses RMW instructions into a hybrid one. We then provide experimental evidence on the effectiveness of using hybrid primitives in the implementation of spin locks, barriers and lock-free queues, in microbenchmarks and parallel applications on a SGI Origin 2000.

This paper investigates the performance implications of data placement in OpenMP programs running on modern ccNUMA multiprocessors. Data locality and minimization of the rate of remote memory accesses are critical for sustaining high performance on these systems. We show that due to the low remote-to-local memory access latency ratio of state-of-the-art ccNUMA architectures, reasonably balanced page placement schemes, such as round-robin or random distribution of pages incur modest performance losses. We also show that performance leaks stemming from suboptimal page placement schemes can be remedied with a smart user-level page migration engine. The main body of the paper describes how the OpenMP runtime environment can use page migration for implementing implicit data distribution and redistribution schemes without programmer intervention. Our experimental results support the effectiveness of these mechanisms and provide a proof of concept that there is no need to introduce data distribution directives in OpenMP and warrant the portability of the programming model.

This paper assesses the performance and scalability of several software synchronization algorithms, as well as the interrelationship between synchronization, multiprogramming and parallel job scheduling, on ccNUMA systems.Using the SGl Origin2000, we evaluate synchronization algorithms for spin locks, lock-free concurrent queues, and barriers.We analyze the sensitivity of synchronization algorithms to the hardware implementation of elementary synchronization primitives and investigate in-depth the architectural implications and particularly the tradeoffs between implementing synchronization primitives with cacheable synchronization variables or at-memory.The architectural study enables us to contribute scalable, customized implementations of synchronization algorithms, including a hybrid scheduler-conscious queue lock and a lock-free queue.We also evaluate different combinations of synchronization algorithms, synchronization disciplines that cope with the effects of multiprogramming and different parallel job scheduling strategies, using the Cellular IEUX operating system as a case study. introductionCache Coherent Non Uniform Memory Access (ccNUMA) architectures have recently attracted considerable research and commercial interest, as they present strong advantages in the direction of achieving high performance.At the same time, synchronization is still an intrusive source of bottlenecks in parallel programs for shared memory.The importance of synchronization has motivated a vast amount of research efforts, which contributed several efficient algorithms for tightly-coupled small-scale symmetric multiprocessors (SMPs), as well as scalable algorithms for distributed memory multiprocessors.Whether these solutions are still sufficient for modern ccNUMA systems remains an open and important question.This paper addresses some significant issues of synchronization on ccNUMA systems.In this direction, we conduct a thorough architectural evaluation of software synchronization algorithms both standalone and in conjunction with spinning and scheduler-conscious disciplines, embedded in synchronization algorithms to cope with the interferences of multiprogramming and the operating sys-Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distribuled for profit or commercial advantage and that copies hear this notice and the I'ull citation on the tirst page.To copy otherwise, to republish, to post WI xrvcrs or to wdistrihutc to lists.requires prior specific permission andior a fee.

Multiprocessor systems are increasingly becoming the systems of choice for low and high-end servers, running such diverse tasks as number crunching, large-scale simulations, data base engines and world wide web server applications.With such diverse workloads, system utilization and throughpuf as well as execution time become important performance metrics.In this paper we present efficient kernel scheduling policies and propose a new kernel-user interface aiming at supporting efficient parallel execution in diverse workload environments.Our approach relies on support for user level threads which are used to exploit parallelism within applications, and a two-level scheduling policy which coordinates the number of resources allocated by the kernel with the number of threads generated by each application.We compare our scheduling policies with the native gang scheduling policy of the IRIX 6.4 operating system on a Silicon Graphics Ori-gin2000.Our experimental results show substantial performance gains in terms of overall workload execution times, individual application execution times, and cache performance.

The problem of minimizing the number of interstreet crossings in single-row routing, known to be intractable in the sense of NP-completeness is studied. An efficient heuristic algorithm for solving this problem is presented. The worst-case computational complexity of the algorithm is O(mn+m/sup 3/), where n is the number of nodes and m>

The importance of problem solving environments (PSEs) for scientific computing is becoming increasingly apparent. The main components of such a PSE are the user interface and the expert system. The authors have proposed a task-level architecture called NAIS which attempts to capture the common nucleus of particularities of expert systems in scientific computing. They report on the application of NAIS to the very important area of elliptic PDEs (partial differential equations), initially using the VAX-II system as the target architecture for the PDE library. As the resulting expert system is divided to an architecture dependent and independent part, it can be easily adapted to other architectures. Finally, this development constitutes an interesting effort of knowledge engineering in scientific computing using a task-level architecture.>

We report on the design and development of a Run Time Support System (RTS) which overcomes known disadvantages of other existing systems. The RTS is independent of the configuration - if the system is reconfigured there is no need to change user's processes. It supports both synchronous and asynchronous communication.

An algorithm for approximating certain classes of elliptic partial differential equations on a rectangle is presented.The algorithm uses high-order 9-point difference approximations to the Helmholtz-type (fourth-order) or Polsson (sixth-order) equations and the fast Fourier transform.Compared to efficient second-order fast direct methods for smooth problems, the execution time is reduced by a large factor, typically 50 for the Helmholtz-type equations and over 100 for the Poisson problem.Comparisons with two high-order fast direct methods indicate the superiority of the algorithm.

article Free AccessArtifacts Evaluated & ReusableArtifacts Available Share on Algorithm 543: FFT9, Fast Solution of Helmholtz-Type Partial Differential Equations [D3] Authors: E. N. Houstis Department of Computer Science, Purdue University, West Lafayette, IN Department of Computer Science, Purdue University, West Lafayette, INView Profile , T. S. Papatheodorou Department of Mathematics, Clarkson College of Technology, Potsdam, NY Department of Mathematics, Clarkson College of Technology, Potsdam, NYView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 5Issue 4Dec. 1979 pp 490–493https://doi.org/10.1145/355853.355865Online:01 December 1979Publication History 7citation402DownloadsMetricsTotal Citations7Total Downloads402Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF