Journal articles: 'Parallel Random Access Machine'

1

Tiskin, Alexandre. "The bulk-synchronous parallel random access machine." Theoretical Computer Science 196, no. 1-2 (1998): 109–30. http://dx.doi.org/10.1016/s0304-3975(97)00197-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

TRAHAN, JERRY L., and HOSANGADI BHANUKUMAR. "PARALLEL RANDOM ACCESS MACHINES WITHOUT BOOLEAN OPERATIONS." Parallel Processing Letters 04, no. 01n02 (1994): 117–24. http://dx.doi.org/10.1142/s0129626494000132.

Full text

Abstract:

The class of problems solved within given time and processor bounds on a Parallel Random Access Machine (PRAM) varies with the instruction set. Previous research has classified the contributions of various instructions, such as multiplication, shifts, and string manipulation operations, to the PRAM. This paper examines the significant contribution of Boolean operations, which play essential roles in many PRAM algorithms and in simulations by the PRAM of other models of computation.

APA, Harvard, Vancouver, ISO, and other styles

3

COSNARD, MICHEL, and AFONSO FERREIRA. "ON THE REAL POWER OF LOOSELY COUPLED PARALLEL ARCHITECTURES." Parallel Processing Letters 01, no. 02 (1991): 103–11. http://dx.doi.org/10.1142/s0129626491000057.

Full text

Abstract:

We propose new models of SIMD distributed memory parallel computers. We define concurrent read/write access also for machines other than PRAM. Our goal is to unify the description of abstract models of parallel machines with the aim of building a complexity theory where all models can be soundly compared. As an example, we introduce the Hypercube Random Access Machine with concurrent read/write capabilities, and show that it can solve some problems faster than the PRAM.

APA, Harvard, Vancouver, ISO, and other styles

4

Breslauer, Dany, Artur Czumaj, Devdatt P. Dubhashi, and Friedhelm Meyer auf der Heide. "Transforming comparison model lower bounds to the parallel-random-access-machine." Information Processing Letters 62, no. 2 (1997): 103–10. http://dx.doi.org/10.1016/s0020-0190(97)00032-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Bellantoni, Stephen J. "Parallel random access machines with bounded memory wordsize." Information and Computation 91, no. 2 (1991): 259–73. http://dx.doi.org/10.1016/0890-5401(91)90069-e.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Behnezhad, Soheil, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, Vahab Mirrokni, and Warren Schudy. "Massively Parallel Computation via Remote Memory Access." ACM Transactions on Parallel Computing 8, no. 3 (2021): 1–25. http://dx.doi.org/10.1145/3470631.

Full text

Abstract:

We introduce the Adaptive Massively Parallel Computation (AMPC) model, which is an extension of the Massively Parallel Computation (MPC) model. At a high level, the AMPC model strengthens the MPC model by storing all messages sent within a round in a distributed data store. In the following round, all machines are provided with random read access to the data store, subject to the same constraints on the total amount of communication as in the MPC model. Our model is inspired by the previous empirical studies of distributed graph algorithms [8, 30] using MapReduce and a distributed hash table service [17]. This extension allows us to give new graph algorithms with much lower round complexities compared to the best-known solutions in the MPC model. In particular, in the AMPC model we show how to solve maximal independent set in O (1) rounds and connectivity/minimum spanning tree in O (log log m / n n rounds both using O ( n δ ) space per machine for constant δ < 1. In the same memory regime for MPC, the best-known algorithms for these problems require poly log n rounds. Our results imply that the 2-C YCLE conjecture, which is widely believed to hold in the MPC model, does not hold in the AMPC model.

APA, Harvard, Vancouver, ISO, and other styles

7

KhurramPasha, Madiha, Maryam Feroze, and Khurram Ahmad Pasha. "A Parallel Random Access Machine (PRAM) Model for English Language Recognizer (PRAM-ELR)." International Journal of Computer Applications 118, no. 6 (2015): 12–18. http://dx.doi.org/10.5120/20749-3139.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Leiserson, Charles E., and Bruce M. Maggs. "Communication-efficient parallel algorithms for distributed random-access machines." Algorithmica 3, no. 1-4 (1988): 53–77. http://dx.doi.org/10.1007/bf01762110.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Trahan, J. L., V. Ramachandran, and M. C. Loui. "Parallel Random Access Machines with both Multiplication and Shifts." Information and Computation 110, no. 1 (1994): 96–118. http://dx.doi.org/10.1006/inco.1994.1025.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Trahan, Jerry L., Michael C. Loui, and Vijaya Ramachandran. "Multiplication, division, and shift instructions in parallel random access machines." Theoretical Computer Science 100, no. 1 (1992): 1–44. http://dx.doi.org/10.1016/0304-3975(92)90362-j.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Fricke, J. Robert. "Reverse-time migration in parallel: A tutorial." GEOPHYSICS 53, no. 9 (1988): 1143–50. http://dx.doi.org/10.1190/1.1442553.

Full text

Abstract:

A reverse-time migration is implemented on a fine-grain or massively parallel computer. With fine-grain architectures many processors are distributed throughout the memory space and can operate on data “in place.” In addition, via a general communication system, any processor can access data from anywhere in the entire memory-processor space. Thus, operations on both local and global data elements are possible. These capabilities are controlled by parallel language constructs which allow parallel variable declaration, parallel arithmetic operation, and parallel random memory access. Reverse-time migration was programmed on a fine-grain machine with these hardware and software features. The reverse-time migration process had a speed improvement of two orders of magnitude relative to a state-of-the-art serial machine. At least another order of magnitude performance can be achieved with currently available floating-point processors. Similar increases in performance are expected for other seismic processes such as velocity estimation, data interpolation, 2-D filtering, and others.

APA, Harvard, Vancouver, ISO, and other styles

12

Cho, Ok-Hyeong, and Robert M. Colomb. "Associative random access machines and data-parallel multiway binary-search join." Future Generation Computer Systems 13, no. 6 (1998): 451–67. http://dx.doi.org/10.1016/s0167-739x(97)00024-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Jogalekar, Usha A., and Akhil Mangla. "Idea Generation Algorithm Based Systems." Advanced Materials Research 403-408 (November 2011): 3937–45. http://dx.doi.org/10.4028/www.scientific.net/amr.403-408.3937.

Full text

Abstract:

Parallel algorithms and parallel processing have revolutionized the machine’s performance and output efficiency. Parallel Random Access Machines are being used excessively for complex input processing and effective output data generation. PRAM algorithms are a class of algorithms defined for parallel computation in polynomial time complexity. Thought process is one of the key procedure that distinctly identifies humans rather animals from machines. Machines proposed to be effective computers have failed when it has come in light to learn and produce new ideas. The study here proposes the Idea Generation Algorithm with all necessary details. The algorithm uses parallel set of processors with a systolic array for data processing. The recognition of optimal output based on the associated weights and the feedback provided by to self-organizing neural network. The network provided with an unsupervised learning is proposed to provide the machine with its own set of ideas thus resulting in achievement of “thought process” in Machines. The algorithm stands as a template for any thought process development and identification in machines. Any system with capability and use of idea generation algorithm shall be with inherent learning and intelligence.

APA, Harvard, Vancouver, ISO, and other styles

14

NIVAT, M., and A. SAOUDI. "PARALLEL RECOGNITION OF HIGH DIMENSIONAL IMAGES." International Journal of Pattern Recognition and Artificial Intelligence 06, no. 02n03 (1992): 285–91. http://dx.doi.org/10.1142/s0218001492000175.

Full text

Abstract:

We investigate the complexity of the recognition of images generated by a class of context-free image grammars. We show that the sequential time complexity of the recognition of an n × n image as generated by a context-free grammar is O(nM(n)), where M(n) is the time to multiply two boolean n × n matrices. The space complexity of this recognition is O(n3). Using a parallel random access machine (i.e. PRAM), the recognition can be done in O( log 2(n)) time with n7 processors or in O(n log 2(n)) time with n6 processors. We also introduce high dimensional context-free grammars and prove that their recognition problem is polylogarithmic.

APA, Harvard, Vancouver, ISO, and other styles

15

XIROUCHAKIS, PAUL C., PEARL Y. WANG, and OPHIR FRIEDER. "DATA PARALLEL VISUAL RECONSTRUCTION AND PARTITIONING ALGORITHMS." Parallel Processing Letters 03, no. 03 (1993): 267–77. http://dx.doi.org/10.1142/s0129626493000319.

Full text

Abstract:

Data parallel visual reconstruction and partitioning algorithms and the associated code are developed for a vector random access machine (V-RAM). Finite element algorithms are constructed for solving the one-dimensional visual reconstruction problem with the input data consisting of a symmetrical top hat loading for the modeling of interacting step discontinuities. The advantage of the V-RAM implementation is the general code applicability to a variety of architectures. A specific implementation is performed on a Distributed Array Processor (DAP) simulator on the VAX 6000–420. Execution times on the DAP simulator are obtained and are found to be in agreement with the algorithmic complexities of the V-RAM code.

APA, Harvard, Vancouver, ISO, and other styles

16

Gnatowski, Andrzej, and Teodor Niżyński. "A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process." Applied Sciences 11, no. 17 (2021): 8083. http://dx.doi.org/10.3390/app11178083.

Full text

Abstract:

Welding frames with differing geometries is one of the most crucial stages in the production of high-end bicycles. This paper proposes a parallel algorithm and a mixed integer linear programming formulation for scheduling a two-machine robotic welding station. The time complexity of the introduced parallel method is O(log2n) on an n3-processor Exclusive Read Exclusive Write Parallel Random-Access Machine (EREW PRAM), where n is the problem size. The algorithm is designed to take advantage of modern graphics cards to significantly accelerate the computations. To present the benefits of the parallelization, the algorithm is compared to the state of art sequential method and a solver-based approach. Experimental results show an impressive speedup for larger problem instances—up to 314 on a single Graphics Processing Unit (GPU), compared to a single-threaded CPU execution of the sequential algorithm.

APA, Harvard, Vancouver, ISO, and other styles

17

Cook, Stephen, Cynthia Dwork, and Rüdiger Reischuk. "Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes." SIAM Journal on Computing 15, no. 1 (1986): 87–97. http://dx.doi.org/10.1137/0215006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

TRAHAN, JERRY L., and SUNDARARAJAN VEDANTHAM. "ANALYSIS OF PRAM INSTRUCTION SETS FROM A LOG COST PERSPECTIVE." International Journal of Foundations of Computer Science 05, no. 03n04 (1994): 231–46. http://dx.doi.org/10.1142/s0129054194000128.

Full text

Abstract:

The log cost measure has been viewed as a more reasonable method of measuring the time complexity of an algorithm than the unit cost measure. The more widely used unit cost measure becomes unrealistic if the algorithm handles extremely large integers. Parallel machines have not been examined under the log cost measure. In this paper, we investigate the Parallel Random Access Machine under the log cost measure. Let the instruction set of a basic PRAM include addition, subtraction, and Boolean operations. We relate resource-bounded complexity classes of log cost PRAMs to complexity classes of Turing machines and circuits. We also relate log cost PRAMs with different instruction sets by simulations that are much more efficient than possible in the unit cost case. Let LCRCWk(CRCWk) denote the class of languages accepted by a log cost (unit cost) basic CRCW PRAM in O( log k n) time with the polynomial in n number of processors. We position the log cost PRAM in the hierarchy of parallel complexity classes as: ACk=CRCWk⊆(NCk+1, LCRCWk+1)⊆ACk+1=CRCWk+1.

APA, Harvard, Vancouver, ISO, and other styles

19

Dietzfelbinger, Martin, Mirosław Kutyłowski, and Rüdiger Reischuk. "Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines." SIAM Journal on Computing 25, no. 6 (1996): 1196–230. http://dx.doi.org/10.1137/s0097539791224285.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Parberry, Ian, and Peiyuan Yan. "Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes." SIAM Journal on Computing 20, no. 1 (1991): 88–99. http://dx.doi.org/10.1137/0220005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

FORSELL, MARTTI. "ON THE PERFORMANCE AND COST OF SOME PRAM MODELS ON CMP HARDWARE." International Journal of Foundations of Computer Science 21, no. 03 (2010): 387–404. http://dx.doi.org/10.1142/s0129054110007325.

Full text

Abstract:

The Parallel Random Access Machine is a very strong model of parallel computing that has resisted cost-efficient implementation attempts for decades. Recently, the development of VLSI technology has provided means for indirect on-chip implementation, but there are different variants of the PRAM model that provide different performance, area and power figures and it is not known how their implementations compare to each others. In this paper we measure the performance and estimate the cost of practical implementations of four PRAM models including EREW, Limited Arbitrary CRCW, Full Arbitrary CRCW, Full Arbitrary Multioperation CRCW on our Eclipse chip multiprocessor framework. Interestingly, the most powerful model shows the lowest simulation cost and highest performance/area and performance/power figures.

APA, Harvard, Vancouver, ISO, and other styles

22

CHAN, I. W., and D. K. FRIESEN. "PARALLEL ALGORITHMS FOR SOME DOMINANCE PROBLEMS BASED ON THE PRAM MODEL." International Journal of Computational Geometry & Applications 03, no. 04 (1993): 367–82. http://dx.doi.org/10.1142/s0218195993000245.

Full text

Abstract:

Two parallel geometric algorithms based on the idea of point domination are presented. The first algorithm solves the d-dimensional isothetic rectangles intersection counting problem of input size N/2d, where d>1 and N is a multiple of 2d, in O( log d−1 N) time and O(N log N) space. The second algorithm solves the direct dominance reporting problem for a set of N points in the plane in O( log N+J) time and O(N log N) space, where J denotes the maximum of the number of direct dominances reported by any single point in the set. Both algorithms make use of the EREW PRAM (Exclusive Read Exclusive Write Parallel Random Access Machine) consisting of O(N) processors as the computational model.

APA, Harvard, Vancouver, ISO, and other styles

23

NIEDERMEIER, ROLF, and PETER ROSSMANITH. "ON OPTIMAL OROW-PRAM ALGORITHMS FOR COMPUTING RECURSIVELY DEFINED FUNCTIONS." Parallel Processing Letters 05, no. 02 (1995): 299–309. http://dx.doi.org/10.1142/s012962649500028x.

Full text

Abstract:

We investigate parallel algorithms to compute recursively defined functions. Our computational model are parallel random access machines (PRAM's). We preferably make use of the OROW-PRAM (owner read, owner write), a model supposed to be even weaker and more realistic than the EREW-PRAM (exclusive read, exclusive write) and that still provides the opportunities of a completely connected processor network. For OROW-PRAM's we show that our parallel algorithms are work-optimal.

APA, Harvard, Vancouver, ISO, and other styles

24

Reischuk, Rüdiger. "Simultaneous WRITES of parallel random access machines do not help to compute simple arithmetic functions." Journal of the ACM 34, no. 1 (1987): 163–78. http://dx.doi.org/10.1145/7531.22944.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Lingas, Andrzej, and Anil Maheshwari. "A Simple Optimal Parallel Algorithm for Reporting Paths in a Tree." Parallel Processing Letters 07, no. 01 (1997): 3–11. http://dx.doi.org/10.1142/s0129626497000036.

Full text

Abstract:

We present optimal parallel solutions to reporting paths between pairs of nodes in an n-node tree. Our algorithms are deterministic and designed to run on an exclusive read exclusive write parallel random-access machine (EREW PRAM). In particular, we provide a simple optimal parallel algorithm for preprocessing the input tree such that the path queries can be answered efficiently. Our algorithm for preprocessing runs in O( log n) time using O(n/ log n) processors. Using the preprocessing, we can report paths between k node pairs in O( log n + log k) time using O(k + (n + S)/ log n) processors on an EREW PRAM, where S is the size of the output. In particular, we can report the path between a single pair of distinct nodes in O( log n) time using O(L/ log n) processors, where L denotes the length of the path.

APA, Harvard, Vancouver, ISO, and other styles

26

LOOGES, PETER J., and STEPHAN OLARIU. "A PRACTICAL PLATFORM FOR CREW EMULATION." Parallel Processing Letters 03, no. 02 (1993): 139–45. http://dx.doi.org/10.1142/s0129626493000174.

Full text

Abstract:

The Parallel Random Access Machine or PRAM model, has been a much employed parallel algorithm development tool for a number of years. As such, many important problems have been solved on this model. Accordingly, considerable attention has been given to the process of simulating PRAM models on more realistic architectures. The purpose of this paper is to present an efficient simulation of the Concurrent Read Exclusive Write PRAM model by the crossbar connected machine (CCM). In addition to simulation, it is proven that all lower bounds for the CREW PRAM directly apply to the CCM. This is the first presentation of algorithmic lower bounds for a crossbar based model. The buses of the network are assumed to have a broadcast delay of δ(n). Recent implementations of the crossbar network in CMOS VLSI technology support the viability of the CCM model. It is the communication flexibility of the crossbar network which supports the PRAM simulations in a very straightforward manner without the complex interconnection systems or high overhead algorithms of many prior simulations.

APA, Harvard, Vancouver, ISO, and other styles

27

Fich, Faith E., Russell Impagliazzo, Bruce Kapron, Valerie King, and Mirosław Kutyłowski. "Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution." Journal of Computer and System Sciences 53, no. 1 (1996): 104–11. http://dx.doi.org/10.1006/jcss.1996.0052.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

HIGHAM, LISA, and ERIC SCHENK. "PRAM MEMORY ALLOCATION AND INITIALIZATION." Parallel Processing Letters 03, no. 03 (1993): 291–99. http://dx.doi.org/10.1142/s0129626493000332.

Full text

Abstract:

Two techniques for managing memory on a parallel random access machine (PRAM) are presented. One is a scheme for an n/log n processor EREW PRAM that dynamically allocates and deallocates up to n records of the same size in O(log n) time. The other is a simulation of a PRAM with initialized memory by one with uninitialized memory. A CREW PRAM variant of the technique justifies the assumption that memory can be assumed to be appropriately initialized with no asymptotic increase in time but a factor of n increase in space. An EREW PRAM solution incurs a factor of O(log n) increase in time but only a constant factor increase in space.

APA, Harvard, Vancouver, ISO, and other styles

29

Gromey, Dmitry Dmitrievich. "ALGORITHMS FOR MANAGING THE LOGICAL STRUCTURE OF THE DATABASE USING A PARAMETRIC MODEL OF COMPETITIVE ACCESS TO QUERIES BASED ON THE RANDOM FOREST METHOD." Computational nanotechnology 6, no. 2 (2019): 41–47. http://dx.doi.org/10.33693/2313-223x-2019-6-2-41-47.

Full text

Abstract:

In article discusses the approach to development of mathematical software for support the process of managing the data schema in relational DBMS in terms of processing of parallel queries stream that compete for data in the hierarchy of the DBMS core memory. The necessity of the formation of a parametric model of queries competitive access. Briefly discusses methods of machine learning, allowing to solve the problem of regression recovery. The use of the random forest method as the most universal method of approximation of arbitrary functions is substantiated. A method of forming a parametric model of competitive access based on the random forest method, as well as an approach with the ensemble of sets of decision trees, which allows to provide the required generalizing ability and stability of the model to partial features and diversity of all types of queries received at the input of the DBMS. The stages of the developed algorithms are presented: ranking query parameters by total execution time and automatic data distribution, allowing you to go from approximating the target system with linear-continuous functions to a set of logical data schema objects, ordered by their effect on time, total query execution time, reducing multi-criteria optimization task to a task optimization by one criterion.

APA, Harvard, Vancouver, ISO, and other styles

30

BEAME, PAUL, MIROSŁAW KUTYŁOWSKI, and MARCIN KIK. "INFORMATION BROADCASTING BY EXCLUSIVE-READ PRAMS." Parallel Processing Letters 04, no. 01n02 (1994): 159–69. http://dx.doi.org/10.1142/s012962649400017x.

Full text

Abstract:

We consider the problem of copying information stored initially in a single memory cell by Exclusive Read Exclusive Write Parallel Random Access Machines (EREW PRAMs). We prove lower bounds for this problem and present algorithms matching them tightly (in many cases up to an additive constant). The bounds presented depend on the number of cells used and size of information copied. The lower bounds apply also to functions where a change of a single argument influences the output in many memory locations.

APA, Harvard, Vancouver, ISO, and other styles

31

MOCHURAD, LESIA, and ANDRII ILKIV. "A NOVEL METHOD OF MEDICAL CLASSIFICATION USING PARALLELIZATION ALGORITHMS." Computer systems and information technologies, no. 1 (April 14, 2022): 23–31. http://dx.doi.org/10.31891/csit-2022-1-3.

Full text

Abstract:

Methods of machine learning in the medical field are the subject of significant ongoing research, which mainly focuses on modeling certain human actions, thought processes or disease recognition. Other applications include biomedical systems, which include genetics and DNA analysis. The purpose of this paper is the implementation of machine learning methods – Random Forest and Decision Tree, further parallelization of these algorithms to achieve greater accuracy of classification and reduce the time of training of these classifiers in the field of medical data processing, determining the presence of human cardiovascular disease. The paper conducts research using machine learning methods for data processing in medicine in order to improve the accuracy and execution time using parallelization algorithms. Classification is an important tool in today's world, where big data is used to make various decisions in government, economics, medicine, and so on. Researchers have access to vast amounts of data, and classification is one of the tools that helps them understand data and find certain patterns in it. The paper used a dataset consisting of records of 70000 patients and containing 12 attributes. Analysis and preliminary data preparation were performed. The Random Forest algorithm is parallelized using the sklearn library functional. The time required to train the model was reduced by 4.4 times when using 8 parallel streams, compared with sequential training. This algorithm is also parallelized based on CUDA. As a result, the time required to train the model was reduced by 83.4 times when using this technology on the GPU. The paper calculates the acceleration and efficiency coefficients, as well as provides a detailed comparison with a sequential algorithm.

APA, Harvard, Vancouver, ISO, and other styles

32

MAHESHWARI, ANIL, and JÖRG-RÜDIGER SACK. "SIMPLE OPTIMAL ALGORITHMS FOR RECTILINEAR LINK PATH AND POLYGON SEPARATION PROBLEMS." Parallel Processing Letters 09, no. 01 (1999): 31–42. http://dx.doi.org/10.1142/s0129626499000062.

Full text

Abstract:

The link metric, defined on a constrained region R of the plane, sets the distance between a pair of points in R to equal the minimum number of line segments or links needed to construct a path in R between the point pair. The minimum rectilinear link path problem considered here is to compute a rectilinear path consisting of the minimum number of links between two points in R, when R is inside an n-sided rectilinear simple polygon. In this paper we present optimal sequential and parallel algorithms to compute a minimum rectilinear link path in a trapezoided region R. Our parallel algorithm requires O( log n) time using a total of O(n) operations. The complexity of our algorithm matches that of the algorithm of McDonald and Peters [19]. By exploiting the dual structure of the trapezoidation of R, we obtain a conceptually simple and easy to implement algorithm. As applications of our techniques we provide an optimal solution to the minimum nested polygon problem and the minimum polygon separation problem. The minimum nested polygon problem asks for finding a rectilinear polygon, with minimum number of sides, that is nested between two given rectilinear polygons one of which is contained in the other. The minimum polygon separation problem asks for computing a minimum number of orthogonal lines and line segments that separate two given non-intersecting simple rectilinear polygons. All parallel algorithms are deterministic, designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM), and are optimal.

APA, Harvard, Vancouver, ISO, and other styles

33

Burkhardt, Paul. "Optimal Algebraic Breadth-First Search for Sparse Graphs." ACM Transactions on Knowledge Discovery from Data 15, no. 5 (2021): 1–19. http://dx.doi.org/10.1145/3446216.

Full text

Abstract:

There has been a rise in the popularity of algebraic methods for graph algorithms given the development of the GraphBLAS library and other sparse matrix methods. An exemplar for these approaches is Breadth-First Search (BFS). The algebraic BFS algorithm is simply a recurrence of matrix-vector multiplications with the n × n adjacency matrix, but the many redundant operations over nonzeros ultimately lead to suboptimal performance. Therefore an optimal algebraic BFS should be of keen interest especially if it is easily integrated with existing matrix methods. Current methods, notably in the GraphBLAS, use a Sparse Matrix masked-Sparse Vector multiplication in which the input vector is kept in a sparse representation in each step of the BFS, and nonzeros in the vector are masked in subsequent steps. This has been an area of recent research in GraphBLAS and other libraries. While in theory, these masking methods are asymptotically optimal on sparse graphs, many add work that leads to suboptimal runtime. We give a new optimal, algebraic BFS for sparse graphs, thus closing a gap in the literature. Our method multiplies progressively smaller submatrices of the adjacency matrix at each step. Let n and m refer to the number of vertices and edges, respectively. On a sparse graph, our method takes O ( n ) algebraic operations as opposed to O ( m ) operations needed by theoretically optimal sparse matrix approaches. Thus, for sparse graphs, it matches the bounds of the best-known sequential algorithm, and on a Parallel Random Access Machine, it is work-optimal. Our result holds for both directed and undirected graphs. Compared to a leading GraphBLAS library, our method achieves up to 24x faster sequential time, and for parallel computation, it can be 17x faster on large graphs and 12x faster on large-diameter graphs.

APA, Harvard, Vancouver, ISO, and other styles

34

Lisowski, Filip, and Edward Lisowski. "Optimization of ER8 and 42CrMo4 Steel Rail Wheel for Road–Rail Vehicles." Applied Sciences 10, no. 14 (2020): 4717. http://dx.doi.org/10.3390/app10144717.

Full text

Abstract:

Railway track maintenance services aim to shorten the time of removing failures on the railways. One of the most important element that shorten the repair time is the quick access to the failure site with an appropriate equipment. The use of road-rail vehicles is becoming increasingly important in this field. In this type of constructions, it is possible to use proven road vehicles such as self-propelled machines or trucks running on wheels with tires. Equipping these vehicles with a parallel rail drive system allows for quick access to the failure site using both roads and railways. Steel rail wheels of road-rail vehicles are designed for specific applications. Since the total weight of vehicle is a crucial parameter for roadworthiness, the effort is made to minimize the mass of rail wheels. The wheel under consideration is mounted directly on the hydraulic motor. This method of assembly is structurally convenient, as no shafts or intermediate couplings are required. On the other hand, it results in strict requirements for the wheel geometry and can cause significant stress concentration. Therefore, the problem of wheel geometry optimization is discussed. Consideration is given to the use of ER8 steel for railway application and 42CrMo4 high-strength steel. Finite element analysis within Ansys software and various optimization tools and methods, such as random tool, subproblem approximation method and first-order method are applied. The obtained results allow to minimize the rail wheel mass with respect to the used material. Moreover, computational demands and methods leading to the best results are compared.

APA, Harvard, Vancouver, ISO, and other styles

35

Zalavadia, Hardikkumar, and Eduardo Gildin. "Two-Step Predict and Correct Non-Intrusive Parametric Model Order Reduction for Changing Well Locations Using a Machine Learning Framework." Energies 14, no. 6 (2021): 1765. http://dx.doi.org/10.3390/en14061765.

Full text

Abstract:

The objective of this paper is to develop a two-step predict and correct non-intrusive Parametric Model Order Reduction (PMOR) methodology for the problem of changing well locations in an oil field that can eventually be used for well placement optimization to gain significant computational savings. In this work, we propose a two-step PMOR procedure, where, in the first step, a Proper Orthogonal Decomposition (POD)-based strategy that is non-intrusive to the simulator source code is introduced, as opposed to the convention of using POD as a simulator intrusive procedure. The non-intrusiveness of the proposed technique stems from formulating a novel Machine Learning (ML)-based framework used with POD. The features of the ML model (Random Forest was used here) are designed such that they take into consideration the temporal evolution of the state solutions and thereby avoid simulator access for the time dependency of the solutions. The proposed PMOR method is global, since a single reduced-order model can be used for all the well locations of interest in the reservoir. We address the major challenge of the explicit representation of the well location change as a parameter by introducing geometry-based features and flow diagnostics-inspired physics-based features. In the second step, an error correction model based on reduced model solutions is formulated to correct for discrepancies in the state solutions at well grid blocks expected from POD basis for new well locations. The error correction model proposed uses Artificial Neural Networks (ANNs) that consider the physics-based reduced model solutions as features, and is proved to reduce the error in QoI (Quantities of Interest), such as oil production rates and water cut, significantly. This workflow is applied to a simple homogeneous reservoir and a heterogeneous channelized reservoir using a section of SPE10 model that showed promising results in terms of model accuracy. Speed-ups of about 50×–100× were observed for different cases considered when running the test scenarios. The proposed workflow for Reduced-Order Modeling is “non-intrusive” and hence can increase its applicability to any simulator used. Additionally, the method is formulated such that all the simulation time steps are independent and hence can make use of parallel resources very efficiently and also avoid stability issues that can result from error accumulation over time steps.

APA, Harvard, Vancouver, ISO, and other styles

36

Noyes, T., and W. E. Dickinson. "The Random-Access Memory Accounting Machine II. The magnetic-disk, random-access memory." IBM Journal of Research and Development 44, no. 1.2 (2000): 16–19. http://dx.doi.org/10.1147/rd.441.0016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Middelburg, Cornelis. "Program Algebra for Random Access Machine Programs." Scientific Annals of Computer Science XXXII, no. 2 (2022): 285–319. http://dx.doi.org/10.7561/sacs.2022.2.285.

Full text

Abstract:

This paper presents an algebraic theory of instruction sequences with instructions for a random access machine (RAM) as basic instructions, the behaviours produced by the instruction sequences concerned under execution, and the interaction between such behaviours and RAM memories. This theory provides a setting for the development of theory in areas such as computational complexity and analysis of algorithms that distinguishes itself by offering the possibility of equational reasoning to establish whether an instruction sequence computes a given function and being more general than the setting provided by any known version of the RAM model of computation. In this setting, a semi-realistic version of the RAM model of computation and a bit-oriented time complexity measure for this version are introduced. Under the time measure concerned, semi-realistic RAMs can be simulated by multi-tape Turing machines with quadratic time overhead.

APA, Harvard, Vancouver, ISO, and other styles

38

Melnyk, Anatoliy. "Parallel Ordered-Access Machine Computational Model and Architecture." Advances in Cyber-Physical Systems 1, no. 2 (2016): 93–101. http://dx.doi.org/10.23939/acps2016.02.093.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Chlebus, Bogdan S., Artur Czumaj, Leszek Ga̧sieniec, Mirosław Kowaluk, and Wojciech Plandowski. "Algorithms for the parallel alternating direction access machine." Theoretical Computer Science 245, no. 2 (2000): 151–73. http://dx.doi.org/10.1016/s0304-3975(99)00280-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Zhang, Zhaoji, Ying Li, Lei Liu, and Wei Hou. "Fixed-Symbol Aided Random Access Scheme for Machine-to-Machine Communications." IEEE Access 7 (2019): 52913–28. http://dx.doi.org/10.1109/access.2019.2912448.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Tribudi, Dimas, and Kae-Won Choi. "Overload Control for Random Access in Cellular Machine-to-Machine Communications." Journal of the Korea institute of electronic communication sciences 9, no. 2 (2014): 181–86. http://dx.doi.org/10.13067/jkiecs.2014.9.2.181.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Jiao, Jian, Liang Xu, Shaohua Wu, Ye Wang, Rongxing Lu, and Qinyu Zhang. "Unequal Access Latency Random Access Protocol for Massive Machine-Type Communications." IEEE Transactions on Wireless Communications 19, no. 9 (2020): 5924–37. http://dx.doi.org/10.1109/twc.2020.2998518.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Chang, Cheng-Shang, and Rhonda Righter. "The optimality of LEPT in parallel machine scheduling." Journal of Applied Probability 31, no. 3 (1994): 788–96. http://dx.doi.org/10.2307/3215156.

Full text

Abstract:

We consider preemptive scheduling on parallel machines where the number of available machines may be an arbitrary, possibly random, function of time. Processing times of jobs are from a family of DLR (decreasing likelihood ratio) distributions, and jobs may arrive at random agreeable times. We give a constructive coupling proof to show that LEPT stochastically minimizes the makespan, and that it minimizes the expected cost when the cost function satisfies certain agreeability conditions.

APA, Harvard, Vancouver, ISO, and other styles

44

Chang, Cheng-Shang, and Rhonda Righter. "The optimality of LEPT in parallel machine scheduling." Journal of Applied Probability 31, no. 03 (1994): 788–96. http://dx.doi.org/10.1017/s0021900200045344.

Full text

Abstract:

We consider preemptive scheduling on parallel machines where the number of available machines may be an arbitrary, possibly random, function of time. Processing times of jobs are from a family of DLR (decreasing likelihood ratio) distributions, and jobs may arrive at random agreeable times. We give a constructive coupling proof to show that LEPT stochastically minimizes the makespan, and that it minimizes the expected cost when the cost function satisfies certain agreeability conditions.

APA, Harvard, Vancouver, ISO, and other styles

45

Alsewaidi, Fatemah, Angela Doufexi, and Dritan Kaleshi. "Enhancing Radio Access Network Performance over LTE-A for Machine-to-Machine Communications under Massive Access." Mobile Information Systems 2016 (2016): 1–16. http://dx.doi.org/10.1155/2016/5187303.

Full text

Abstract:

The expected tremendous growth of machine-to-machine (M2M) devices will require solutions to improve random access channel (RACH) performance. Recent studies have shown that radio access network (RAN) performance is degraded under the high density of devices. In this paper, we propose three methods to enhance RAN performance for M2M communications over the LTE-A standard. The first method employs a different value for the physical RACH configuration index to increase random access opportunities. The second method addresses a heterogeneous network by using a number of picocells to increase resources and offload control traffic from the macro base station. The third method involves aggregation points and addresses their effect on RAN performance. Based on evaluation results, our methods improved RACH performance in terms of the access success probability and average access delay.

APA, Harvard, Vancouver, ISO, and other styles

46

Karimi, F., S. Irrinki, T. Crosby, N. Park, and F. Lombardi. "Parallel testing of multi-port static random access memories." Microelectronics Journal 34, no. 1 (2003): 3–21. http://dx.doi.org/10.1016/s0026-2692(02)00124-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Di, Chong, Bo Zhang, Qilian Liang, Shenghong Li, and Ying Guo. "Learning Automata-Based Access Class Barring Scheme for Massive Random Access in Machine-to-Machine Communications." IEEE Internet of Things Journal 6, no. 4 (2019): 6007–17. http://dx.doi.org/10.1109/jiot.2018.2867937.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Zhang, Jilin, Hangdi Tu, Yongjian Ren, et al. "An Adaptive Synchronous Parallel Strategy for Distributed Machine Learning." IEEE Access 6 (2018): 19222–30. http://dx.doi.org/10.1109/access.2018.2820899.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Tian, Ni, Changle Li, Jun Cheng, Wenwei Yue, and Maofeng Luo. "Decentralized Power Control for an ALOHA-Type Random Multiple Access System with Short Packet Transmission." Wireless Communications and Mobile Computing 2022 (July 22, 2022): 1–10. http://dx.doi.org/10.1155/2022/5428680.

Full text

Abstract:

Machine to machine communication is an important scenario in a 6G communication network. Random multiple access has recently been revisited and considered a key technology for machine to machine communication scenarios due to many advantages such as without coordination setup time. It is a regret that packet collision probability will be extremely higher for random multiple access when massive devices randomly accessing base station. Decentralized power control is an efficient scheme in random multiple access systems which can support intraslot successive interference cancellation to recover multiple collided packets at receivers. However, existing studies of decentralized power control for random multiple access are with the assumption that blocklength of transmitted packets is infinite, which neglects that machine to machine communication is characterized by finite blocklength transmission (i.e., short packet) in 6G. This paper focuses decentralized power control with short packet transmission in random multiple access systems. First, the closed-form expression of signal to interference plus noise ratio (SINR) threshold for short packets is derived. Then, decentralized transmission power profile is defined based on derived SINR threshold of short packets, which can support intraslot successive interference cancellation deciding at receivers for an ALOHA-type random multiple access system. Further, we propose derivation method to maximize system throughput, which can reduce optimization cost. Theoretical findings in this paper can provide valuable benchmark for short packet transmission with decentralized power control in random multiple access systems.

APA, Harvard, Vancouver, ISO, and other styles

50

Jang, Han Seung, Hoon Lee, Munseop Yun, and Daeik Kim. "Machine Learning-Based Detection Mechanism of Random Access Preambles." Journal of Korean Institute of Communications and Information Sciences 46, no. 2 (2021): 264–67. http://dx.doi.org/10.7840/kics.2021.46.2.264.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Parallel Random Access Machine'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles