In this paper, we use the tensor product notation as the framework of a programming methodology for designing block recursive algorithms. We first express a computational problem in its matrix form. Next, we formulate...
详细信息
In this paper, we use the tensor product notation as the framework of a programming methodology for designing block recursive algorithms. We first express a computational problem in its matrix form. Next, we formulate a matrix equation for the matrix of the computational problem. Then, we try to find a solution of the matrix equation such that the solution is composed of simple matrices. Finally, we recursively factorize the subproblem to obtain a tensor product formula representing an algorithm for the given problem. In this methodology, the operations of a tensor product formula can be mapped to language constructs of high-level programming languages. That is, we can generate computer programs, including programs for parallel computers and distributed-memory multiprocessors, from tensor product formulas. In this paper, we use the parallel prefix problem and the discrete Fourier transform problem as examples to illustrate the methodology and derive various parallel prefix and fast Fourier transform algorithms.
The course on programming methodology is integral to computer science and software engineering education. Knowledge graph has been an interesting topic in recent decades, and knowledge graph has propelled its use in s...
详细信息
ISBN:
(纸本)9798400717819
The course on programming methodology is integral to computer science and software engineering education. Knowledge graph has been an interesting topic in recent decades, and knowledge graph has propelled its use in systematically organizing, thoroughly analyzing, and fully leveraging knowledge to become a focal point in teaching research and application, yielding significant progress. Therefore, this paper proposes a method for constructing a knowledge graph tailored to the curriculum. Furthermore, it establishes a comprehensive course knowledge graph, a student capability knowledge graph, and a course resource knowledge graph. Upon this foundation, by leveraging the multi-model database ArangoDB and the visualization framework GraphVIS, a visualized system for a curriculum knowledge graph has been realized. This study aims to offer a reference for the construction and pedagogical approaches of the course, and preliminary applications of the system have received positive feedback.
In this paper, we use the tensor product notation as the framework of a programming methodology for designing block recursive algorithms on various computer networks. In our previous works, we propose a programming me...
详细信息
ISBN:
(纸本)0769516807
In this paper, we use the tensor product notation as the framework of a programming methodology for designing block recursive algorithms on various computer networks. In our previous works, we propose a programming methodology for designing block recursive algorithms on shared-memory and distributed-memory multiprocessors without considering the interconnection of processors. We extend the work to consider the block recursive algorithms on direct networks and multistage interconnection networks. We use parallel prefix computation as an example to illustrate the methodology. First, we represent the prefix computation problem as a computational matrix which may not be suitable for deriving algorithms on specific computer networks. In this methodology, we add two steps to derive tensor product formulas of parallel prefix algorithms on computer networks: (1)decompose the computational matrix into two submatrices, and (2) construct an augmented matrix. The augmented matrix can be factorized so that each term is a tensor product formula and can fit into a specified network topology. With the augmented matrix, the input data is also extended. It means, in addition to the input data, an auxiliary vector as temporary storage is used. The content of temporary storage is relevant to the decomposition of the original computational matrix. We present the methodology to derive various parallel prefix algorithms on hypercube, omega, and baseline networks and veri,, correctness of the resulting tensor product formulas using induction.
Data abstraction has been an important consideration since the mid-1970s, with most research effort directed toward the development of experimental languages, formal specification techniques, and program verification ...
详细信息
Data abstraction has been an important consideration since the mid-1970s, with most research effort directed toward the development of experimental languages, formal specification techniques, and program verification schemes. The role of data abstraction in programming methodology, on the other hand, has received considerably less attention. In particular, the potential benefits of the application of data abstraction principles to conventional programming environments have been all but ignored. A programming methodology based on data abstraction and designed especially for the Fortran programming environment is presented here. [ABSTRACT FROM AUTHOR]
An advanced flexible programming methodology for CNC woodworking machines was developed. As the research starting base, a three-axis CNC woodworking machine was used. The developed methodology is proposed for programm...
详细信息
An advanced flexible programming methodology for CNC woodworking machines was developed. As the research starting base, a three-axis CNC woodworking machine was used. The developed methodology is proposed for programming, simulation, postprocessing, and machining by woodworking machine. This flexible programming method integrates the standard programming based on CAD, CAD/CAM systems, and STEP-NC protocol through different output files, enabling data interoperability during the realization of the machining tasks. The control system for the machine is configured based on the open-architecture software LinuxCNC to verify the flexible programming method and the results obtained. programming verification was realized by simulation on a configured virtual machine in different programming environments and finally on a virtual machine integrated with the control system. The results obtained from the study were evaluated comparatively.
An adaptive program is one that changes its behavior based on the current state of its environment. This notion of adaptivity is formalized and a logic for reasoning about adaptive programs is presented. The logic inc...
详细信息
An adaptive program is one that changes its behavior based on the current state of its environment. This notion of adaptivity is formalized and a logic for reasoning about adaptive programs is presented. The logic includes several composition operators that can be used to define an adaptive program in terms of given constituent programs;programs resulting from these compositions retain the adaptive properties of their constituent programs.
We describe here a programming methodology for multiprocessors that leads to well-structured code, ease of debugging, and, most important, portability among multiprocessors offering quire different synchronization pri...
详细信息
We describe here a programming methodology for multiprocessors that leads to well-structured code, ease of debugging, and, most important, portability among multiprocessors offering quire different synchronization primitives. The emphasis in this paper is on the implementation of this methodology for the Lemur, an eight-processor machine built at Argonne National Laboratory. Included are several complete programs illustrating the methodology.
While the use of global time is an expensive tool to implement, it can simplify the design and description of distributed algorithms. It is demonstrated that, in some cases, global time can be assumed while designing...
详细信息
While the use of global time is an expensive tool to implement, it can simplify the design and description of distributed algorithms. It is demonstrated that, in some cases, global time can be assumed while designing an algorithm, but need not be implemented. In these cases, it can be replaced with Lamport's logical time in a routine fashion, which clearly assures the correctness of the algorithm. The method is illustrated by 3 examples: 1. Chandy and Lamport's distributed snapshot algorithm, 2. Banatre and Lapalme's fair agreement algorithm for the distributed auction system, Enchere, and 3. a new distributed algorithm for restarting from a saved checkpoint state. It is shown that, if a property of a distributed computation is preserved by reorderings that respect event sequences in nodes and channels individually, then that property can be established by an algorithm that assumes global time, but is provided with logical time.
Some views on programming, taken in a wide sense and regarded as a human activity, are presented. Accepting that programs will not only have to be designed and produced, but also modified so as to cater for changing d...
详细信息
Some views on programming, taken in a wide sense and regarded as a human activity, are presented. Accepting that programs will not only have to be designed and produced, but also modified so as to cater for changing demands, it is concluded that the proper, primary aim of programming is, not to produce programs, but to have the programmers build theories of the manner in which the problems at hand are solved by program execution. The implications of such a view of programming on matters such as program life and modification, system development methods, and the professional status of programmers, are discussed.
Dynamic programming solves combinatorial optimization problems by recursive decomposition and tabulation of intermediate results. The first step in the design of a dynamic programming algorithm is to decide on the set...
详细信息
Dynamic programming solves combinatorial optimization problems by recursive decomposition and tabulation of intermediate results. The first step in the design of a dynamic programming algorithm is to decide on the set of tables that will hold optimal solutions to subproblems. This step predetermines the shape of the dynamic programming recurrences as well as the asymptotic efficiency of the algorithm in time and space. We study dynamic programming in a formal framework where design of tables and problem decomposition can be done independently. Our main result shows that choosing a good table design for a given decomposition is an NP-complete problem. A heuristic or approximate approach is therefore needed to automate good table design. We report on a strategy that combines user annotation and a brute force algorithm, which is shown to perform well in a large application. (C) 2006 Elsevier Inc. All rights reserved.
暂无评论