The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

Fast folding and comparison of RNA secondary structures

Summary Computer codes for computation and comparison of RNA secondary structures, the Vienna RNA package, are presented, that are based on dynamic programming algorithms and aim at predictions of structures with minimum free energies as well as at computations of the equilibrium partition functions and base pairing probabilities.An efficient heuristic for the inverse folding problem of RNA is introduced. In addition we present compact and efficient programs for the comparison of RNA secondary structures based on tree editing and alignment.All computer codes are written in ANSI C. They include implementations of modified algorithms on parallel computers with distributed memory. Performance analysis carried out on an Intel Hypercube shows that parallel computing becomes gradually more and more efficient the longer the sequences are.

---

Schnelle Faltung und Vergleich von Sekundärstrukturen von RNA

Zusammenfassung Die im Vienna RNA package enthaltenen Computer Programme für die Berechnung und den Vergleich von RNA Sekundärstrukturen werden präsentiert. Ihren Kern bilden Algorithmen zur Vorhersage von Strukturen minimaler Energie sowie zur Berechnung von Zustandssumme und Basenpaarungswahrscheinlichkeiten mittels dynamischer Programmierung.Ein effizienter heuristischer Algorithmus für das inverse Faltungsproblem wird vorgestellt. Darüberhinaus präsentieren wir kompakte und effiziente Programme zum Vergleich von RNA Sekundärstrukturen durch Baum-Editierung und Alignierung.Alle Programme sind in ANSI C geschrieben, darunter auch eine Implementation des Faltungs-algorithmus für Parallelrechner mit verteiltem Speicher. Wie Tests auf einem Intel Hypercube zeigen, wird das Parallelrechnen umso effizienter je länger die Sequenzen sind.

     

Migration of seismic data

Prospecting for oil and gas resources poses the problem of determining the geological structure of the earth's crust from indirect measurements. Seismic migration is an acoustic image reconstruction technique based on the inversion of the scalar wave equation. Extensive computation is necessary before reliable information can be extracted from large sets of recorded data. In this paper a collection of industrial migration techniques, each giving rise to a data parallel algorithm, is outlined. Computer simulations on synthetic seismic data illustrate the problem and the approach.     

Functional Materials for Memristor-Based Reservoir Computing: Dynamics and Applications

The booming development of artificial intelligence (AI) requires faster physical processing units as well as more efficient algorithms. Recently, reservoir computing (RC) has emerged as an alternative brain-inspired framework for fast learning with low training cost, since only the weights associated with the output layers should be trained. Physical RC becomes one of the leading paradigms for computation using high-dimensional, nonlinear, dynamic substrates. Among them, memristor appears to be a simple, adaptable, and efficient framework for constructing physical RC since they exhibit nonlinear features and memory behavior, while memristor-implemented artificial neural networks display increasing popularity towards neuromorphic computing. In this review, the memristor-implemented RC systems from the following aspects: architectures, materials, and applications are summarized. It starts with an introduction to the RC structures that can be simulated with memristor blocks. Specific interest then focuses on the dynamic memory behaviors of memristors based on various material systems, optimizing the understanding of the relationship between the relaxation behaviors and materials, which provides guidance and references for building RC systems coped with on-demand application scenarios. Furthermore, recent advances in the application of memristor-based physical RC systems are surveyed. In the end, the further prospects of memristor-implemented RC system in a material view are envisaged.     

Emerging MXene-Based Memristors for In-Memory,Neuromorphic Computing,and Logic Operation

Confronted by the difficulties of the von Neumann bottleneck and memory wall, traditional computing systems are gradually inadequate for satisfying the demands of future data-intensive computing applications. Recently, memristors have emerged as promising candidates for advanced in-memory and neuromorphic computing, which pave one way for breaking through the dilemma of current computing architecture. Till now, varieties of functional materials have been developed for constructing high-performance memristors. Herein, the review focuses on the emerging 2D MXene materials-based memristors. First, the mainstream synthetic strategies and characterization methods of MXenes are introduced. Second, the different types of MXene-based memristive materials and their widely adopted switching mechanisms are overviewed. Third, the recent progress of MXene-based memristors for data storage, artificial synapses, neuromorphic computing, and logic circuits is comprehensively summarized. Finally, the challenges, development trends, and perspectives are discussed, aiming to provide guidelines for the preparation of novel MXene-based memristors and more engaging information technology applications.     

A survey on deploying mobile deep learning applications: A systemic and technical perspective

With the rapid development of mobile devices and deep learning, mobile smart applications using deep learning technology have sprung up. It satisfies multiple needs of users, network operators and service providers, and rapidly becomes a main research focus. In recent years, deep learning has achieved tremendous success in image processing, natural language processing, language analysis and other research fields. Despite the task performance has been greatly improved, the resources required to run these models have increased significantly. This poses a major challenge for deploying such applications on resource-restricted mobile devices. Mobile intelligence needs faster mobile processors, more storage space, smaller but more accurate models, and even the assistance of other network nodes. To help the readers establish a global concept of the entire research direction concisely, we classify the latest works in this field into two categories, which are local optimization on mobile devices and distributed optimization based on the computational position of machine learning tasks. We also list a few typical scenarios to make readers realize the importance and indispensability of mobile deep learning applications. Finally, we conjecture what the future may hold for deploying deep learning applications on mobile devices research, which may help to stimulate new ideas.     

Research advances on blockchain-as-a-service: architectures,applications and challenges

Due to the complexity of blockchain technology, it usually costs too much effort to build, maintain and monitor a blockchain system that supports a targeted application. To this end, the emerging “Blockchain as a Service” (BaaS) makes the blockchain and distributed ledgers more accessible, particularly for businesses, by reducing costs and overheads. BaaS combines the high computing power of cloud computing, the pervasiveness of IoT and the decentralization of blockchain, allowing people to build their own applications while ensuring the transparency and openness of the system. This paper surveys the research outputs of both academia and industry. First, it introduces the representative architectures of BaaS systems and then summarizes the research contributions of BaaS from the technologies for service provision, roles, container and virtualization, interfaces, customization and evaluation. The typical applications of BaaS in both academic and practical domains are also introduced. At present, the research on the blockchain is abundant, but research on BaaS is still in its infancy. Six challenges of BaaS are concluded in this paper for further study directions.     

PRIRODA-04: a quantum-chemical program suite. New possibilities in the study of molecular systems with the application of parallel computing

Main characteristics are described of the PRIRODA quantum-chemical program suite designed for the study of complex molecular systems by the density functional theory, at the MP2, MP3, and MP4 levels of multiparticle perturbation theory, and by the coupled-cluster single and double excitations method (CCSD) with the application of parallel computing. A number of examples of calculations are presented.__________Published in Russian in Izvestiya Akademii Nauk. Seriya Khimicheskaya, No. 3, pp. 804–810, March, 2005.     

A parallel implementation of the COLUMBUS multireference configuration interaction program

Summary In this work a parallel implementation of the COLUMBUS MRSDCI program system is presented. A coarse grain parallelization approach using message passing via the portable toolkit TCGMSG is used. The program is very well portable and runs on shared memory machines like the Cray Y-MP, Alliant FX/2800 or Convex C2 and on distributed memory machines like the iPSC/860. Further implementations on a network of workstations and on the Intel Touchstone Delta are in progress. Overall, results are quite satisfactory considering the complexity and the prodigious requirements, especially the I/O bandwidth, of MRCI programs in general. For our largest test case we obtain a speedup of a factor of 7.2 on an eight processor Cray Y-MP for that section of the program (hamiltonian matrix times trial vector product) which has been parallelized. The speedup for one complete diagonalization iteration amounts to 5.9. An absolute speed close to 1 GFLOPS is found. Results for the iPSC/860 show that ordinary disk I/O is certainly not sufficient in order to guarantee a satisfactory performance. As a solution for that problem, the implementation of a fully asynchronous distributed-memory model for certain data files is in preparation. On leave from: Bereich Informatik, Universität Leipzig, Augustusplatz 10/11, O-7010 Leipzig, Germany     

Benchmark studies of the BCRLM reactive scattering code: Implications for accurate quantum calculations

Summary The Bending Corrected Rotating Linear Model (BCRLM), developed by Hayes and Walker, is a simple approximation to the true multidimensional scattering problem for reactions of the type: A + BC AB + C. While the BCRLM method is simpler than methods designed to obtain accurate three-dimensional quantum scattering results, this turns out to be a major advantage in terms of our benchmarking studies. The computer code used to obtain BCRLM scattering results is written for the most part in standard FORTRAN and has been ported to several scalar, vector, and parallel architecture computers including the IBM 3090-600J, the Cray XMP and YMP, the Ardent Titan, IBM RISC System/6000, Convex C-1 and the MIPS 2000. Benchmark results will be reported for each of these machines with an emphasis on comparing the scalar, vector, and parallel performance for the standard code with minimum modifications. Detailed analysis of the mapping of the BCRLM approach onto both shared and distributed memory parallel architecture machines indicates the importance of introducing several key changes in the basic strategy and algorithms used to calculate scattering results. This analysis of the BCRLM approach provides some insights into optimal strategies for mapping three-dimensional quantum scattering methods, such as the Parker-Pack method, onto shared or distributed memory parallel computers.