Search

High-performance computers are used for computation-intensive tasks. It is essential for these systems to simultaneously execute several computation-intensive tasks for efficient and timely system utilization. Since typical tasks have a longer runtime, it is essential to determine the runtime of each task prior to execution and schedule them accordingly. We propose a method for predicting the runtime of MPI-based software. Initially, we analyze the source code of the software by translating the code to finite automata and measuring the state complexity. Next, the runtime of software is trained using a deep neural network (DNN) along with its state complexity. Herein, we propose three models based on DNN, statistics and their hybrid. DNN model is superior in comparison. Additionally, the adaptability of our method is demonstrated by showing that our method can adapt on new environment with 90% accuracy on various software.

It is well known that the copy language \(L = \{ww \mid w \in \varSigma ^*\}\) is not context-free despite its simplicity. We study pseudo-copy languages that are defined to be sets of catenations of two similar strings, and prove non-context-freeness of these languages. We consider the Hamming distance and the edit-distance for the error measure of the two similar strings in pseudo-copy languages. When the error has an upper bound or a fixed value, we show that the pseudo-copy languages are not context-free. Similarly, if the error has a lower bound of at least four, then such languages are not context-free, either. Finally, we prove that all these pseudo-copy languages are context-sensitive.

People use high performance computers (HPCs) for computation-intensive tasks. Often these tasks require a lot of running time of their corresponding softwares. It is important to execute several tasks simultaneously for the system utilization while finishing all tasks within their desired deadlines. Therefore, it is important to know the runtime of each computation-intensive task without executing them in order to schedule the tasks on HPC and obtain better system performance. We propose a method for predicting runtime of MPI-based softwares on HPC using automata theory and deep learning. We first analyze a source code of an input program by representing the code as finite automata and measuring their state complexities. Next, we train the execution runtime of each module of our finite automata using deep neural network (DNN) together with its own state complexity. Then we combine all modules and make a single SW-runtime-prediction model. For experiment, we train the proposed model using OSU benchmark data, HPL and two in-house datasets, and present the usefulness of our model. We also demonstrate the adaptability of our model by updating the current model for new inputs using incremental DNN, which is an important feature for coping with new softwares or new systems.

A distance between two languages is a useful tool to measure the language similarity, and is closely related to the intersection problem as well as the shortest string problem. A parsing expression grammar (PEG) is an unambiguous grammar such that the choice operator selects the first matching in PEG while it can be ambiguous in a context-free grammar. PEGs are also closely related to top-down parsing languages. We consider two problems on parsing expression languages (PELs). One is the r-shortest string problem that decides whether or not a given PEL contains a string of length shorter than r. The other problem is the edit-distance problem of PELs with respect to other language families such as finite languages or regular languages. We show that the r-shortest string problem and the edit-distance problem with respect to finite languages are NEXPTIME-complete, and the edit-distance problem with respect to regular languages is undecidable. In addition, we prove that it is impossible to compute a length bound \(\mathcal {B}(G)\) of a PEG G such that L(G) has a string w of length at most \(\mathcal {B}(G)\).