A Design Space Exploration Framework for Memristor-Based Crossbar Architecture

Authors
Barbareschi, M.; Bosio, A.; O'Connor, I.; Fišer, P.; Traiola, M.
Year
2022
Published
Proceedings of the 2022 25th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS). Piscataway: IEEE, 2022. p. 38-43. ISSN 2473-2117. ISBN 978-1-6654-9431-1.
Type
Proceedings paper
Annotation
In the literature, there are few studies describing how to implement Boolean logic functions as a memristor-based crossbar architecture and some solutions have been actually proposed targeting back-end synthesis. However, there is a lack of methodologies and tools for the synthesis automation. %More in detail, what is missing is a methodology able to optimize a given Boolean logic function for the memristor-based implementation. The main goal of this paper is to perform a Design Space Exploration (DSE) in order to analyze and compare the impact of the most used optimization algorithms on a memristor-based crossbar architecture. %The synthesized circuits are quantified in terms of area, energy consumption, and performance. The results carried out on 102 circuits lead us to identify the best optimization approach, in terms of area/energy/delay. The presented results can also be considered as a reference (benchmarking) for comparing future work.

A fair experimental evaluation of distance correlation side-channel distinguisher

Year
2022
Published
Proceedings of the 11th Mediterranean Conference on Embedded Computing (MECO 2022). Institute of Electrical and Electronics Engineers, Inc., 2022. p. 110-113. ISSN 2637-9511. ISBN 978-1-6654-6828-2.
Type
Proceedings paper
Annotation
Side-channel attacks pose a severe threat to crypto graphic implementations, allowing the attacker to recover secret information based on physical observations of the cryptographic device. Correlation Power Analysis is considered to be one of the most powerful attacks in the non-profiled scenario. In this paper, we consider the distance/Brownian correlation instead of the traditionally used Pearson coefficient. We give a fair comparison of our novel approach attacking AES on three different FPGA platforms and we discuss the distance correlation potential in the context of side-channel analysis.

Ab initio View of Emergent Symplectic Symmetry and Its Crutial Role in Nuclear Dynamics

Authors
Dytrych, T.; Launey, K.D.; Draayer, J.P.; Langr, D.
Year
2022
Published
Bulgarian Journal of Physics. 2022, 49(1), 37-46. ISSN 1310-0157.
Type
Article
Annotation
Results of large-scale first principle nuclear structure studies using the symmetry-adapted no-core shell model are reported. It is shown that nuclei up through the intermediate-mass region display highly regular and ubiquitous patterns of dominant nuclear shapes that vibrate and rotate. This emergent structure is tied to an approximate symplectic Sp (3, R) symmetry, and it is shown to determine dominant features of low-lying states, even in close-to-spherical nuclear states without any recognizable rotational properties.

Approximate arithmetic for modern neural networks and FPGAs

Year
2022
Published
Proceedings of the 11th Mediterranean Conference on Embedded Computing (MECO 2022). Institute of Electrical and Electronics Engineers, Inc., 2022. p. 357-360. ISSN 2637-9511. ISBN 978-1-6654-6828-2.
Type
Proceedings paper
Annotation
Approximate arithmetic is a very important approach for implementing neural networks in embedded hardware. The requirements of real-time applications with respect to the size of deep neural networks force designers to simplify the neural processing elements. Not only the reduction of precision of model parameters to a few bits, but also the use of approximate arithmetic increases computational power and saves on-chip resources beyond exact computation. Since it was shown that linearly approximated functions are suitable for implementing neural networks in hardware, FPGAs have improved. So we decided to re-implement the processing element on a modern FPGA and to present implementation results regarding speed and resource consumption. A neural processing element based on linearly approximated functions was implemented in Vivado and tested on an xc7 FPGA. The results show that the architecture saves significant resources and a clock frequency above 100 MHz can be achieved in pipelined design.

Correlation Power Analysis of SipHash

Authors
Olekšák, M.; Miškovský, V.
Year
2022
Published
Proceedings of the 2022 25th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS). Piscataway: IEEE, 2022. p. 84-87. ISSN 2473-2117. ISBN 978-1-6654-9431-1.
Type
Proceedings paper
Annotation
SipHash is ARX-based pseudorandom function optimized for short inputs. It was developed as a hash table lookup function, but it is also used for MAC generation. At the time of writing, there was no side-channel attack on SipHash known to us. This work is about application of CPA attack on SipHash. Attack was performed on ChipWhisperer CW308 UFO Board with STM32F0 target. Approximately 800 power traces were needed for succesful attack. Leakage information from XOR was used to attack cipher key. The main contribution of this work is power model of binary addition including carry propagation.

CPP11sort: A parallel quicksort based on C++ threading

Authors
Langr, D.; Schovánková, K.
Year
2022
Published
Concurrency and Computation: Practice and Experience. 2022, 34(4), 1-11. ISSN 1532-0626.
Type
Article
Annotation
A new efficient implementation of the multi-threaded quicksort algorithm called CPP11sort is presented. This implementation is built exclusively upon the threading primitives of the C++ programming language itself. The performance of CPP11sort is evaluated and compared with its mainstream competitors provided by GNU, Intel, and Microsoft. It is shown that out of the considered implementations, CPP11sort mostly yields the shortest sorting times and is the only one that is portable to any conforming C++ implementation without a need of external libraries or non-standard compiler extensions. The experimental evaluation with various input data distributions resulted in parallel speedup between 16.1 and 44.2 on a 56-core server and between 6.8 and 14.5 on a 10-core workstation with enabled hyper-threading.

Cultural Diversity and Its Impact on Governance

Authors
Evan, T.; Holý, V.
Year
2022
Published
International Journal of Intercultural Relations. 2022, ISSN 0147-1767.
Type
Article
Annotation
Hofstede’s six cultural dimensions make it possible to measure the culture of countries but are criticized for assuming the homogeneity of each country. In this paper, we propose two measures based on Hofstede’s cultural dimensions which take into account the heterogeneous structure of citizens with respect to their countries of origin. Using these improved measures, we study the influence of heterogeneous culture and cultural diversity on the quality of institutions measured by the six worldwide governance indicators. We use a linear regression model allowing for dependence in spatial and temporal dimensions as well as the high correlation between the governance indicators. Our results show that the effect of cultural diversity improves some of the governance indicators while worsening others depending on the individual Hofstede cultural dimension.

Enhancing Reactive Ad Hoc Routing Protocols with Trust

Year
2022
Published
Future Internet. 2022, 14(1), ISSN 1999-5903.
Type
Article
Annotation
In wireless ad hoc networks, security and communication challenges are frequently addressed by deploying a trust mechanism. A number of approaches for evaluating trust of ad hoc network nodes have been proposed, including the one that uses neural networks. We proposed to use packet delivery ratios as input to the neural network. In this article, we present a new method, called TARA (Trust-Aware Reactive Ad Hoc routing), to incorporate node trusts into reactive ad hoc routing protocols. The novelty of the TARA method is that it does not require changes to the routing protocol itself. Instead, it influences the routing choice from outside by delaying the route request messages of untrusted nodes. The performance of the method was evaluated on the use case of sensor nodes sending data to a sink node. The experiments showed that the method improves the packet delivery ratio in the network by about 70%. Performance analysis of the TARA method provided recommendations for its application in a particular ad hoc network.

Evacuation trials from a double-deck electric train unit: Experimental data and sensitivity analysis

Authors
Najmanová, H.; Kuklík, L.; Pešková, V.; Bukáček, M.; Vašata, D.; Hrabák, P.
Year
2022
Published
Safety Science. 2022, 146 ISSN 0925-7535.
Type
Article
Annotation
Passenger trains represent a challenging environment in emergencies, with specific evacuation conditions resulting from the typical layout and interior design inherent to public transportation vehicles. This paper describes a dataset obtained in a full-scale controlled experiment emulating the emergency evacuation of a double-deck electric unit railcar carried out in Prague in 2018. 15 evacuation trials involving 91 participants were conducted under various evacuation scenarios considering different compositions of passenger crowd, exit widths, and exit types (egress to a high platform, to an open rail line using stairs, and a 750 mm jump without any supporting equipment). The study’s main goals were to collect experimental data on the movement conditions in the railcar and to study the impact of various boundary conditions on evacuation process and total evacuation time. Movement characteristics (exit flows, speeds) and human behaviour (pre-movement activities, exiting behaviours) were also analysed. The data obtained was used to validate and adjust a Pathfinder model to capture important aspects of evacuation from the railcar. Furthermore, a series of simulations using this model was performed to provide sensitivity analysis of the influence of crowd composition, exit width, and exit type on total evacuation time. As a key finding, we can conclude that for the case of a standard exit path (platform or stairs) the width of the main exit had the greatest impact on total evacuation time, however, crowd composition played the prevailing role in evacuation scenarios involving a jump.

Evaluation of power saving methods for low-power WiFi environment sensors

Year
2022
Published
Proceedings of the 11th Mediterranean Conference on Embedded Computing (MECO 2022). Institute of Electrical and Electronics Engineers, Inc., 2022. p. 1-5. ISSN 2637-9511. ISBN 978-1-6654-6828-2.
Type
Proceedings paper
Annotation
Environment sensing devices are all around us and the instruction cycle of these devices is usually simple: wake up, measure data, send them to a central unit or to the cloud and enter deep sleep. These devices also need to last as long as possible on a single charge and when we say single charge, we mean months at least. This leads to one common problem-these devices usually use low data rate networks like ZigBee or LoRa and therefore are not easy to deploy for a common user. There are several ways of achieving low power consumption when using WiFi. This paper describes and evaluates these methods and recommends power-saving methods for the WiFi module ESP8266. This paper also describes the development of a reference low-power device that can sense the environment (temperature, humidity and pressure in this case) and uses 2.4 GHz WiFi. Therefore, this device does not need any sort of gateway and can connect directly to the network most users already have deployed. Current programming allows for quick and easy transmission of the data to an MQTT server. It is easy to quicks tart usage and mass production of the presented prototype. The system is based on the popular ESP8266 as a base for measurement, processing and WiFi communication. For power management, more circuitry is used. The paper presents a full reference schematics of the developed device.

Expanding Normalized Systems from textual domain descriptions using TEMOS

Authors
Šenkýř, D.; Suchánek, M.; Kroha, P.; Mannaert, H.; Pergl, R.
Year
2022
Published
Journal of Intelligent Information Systems. 2022, ISSN 1573-7675.
Type
Article
Annotation
Functional requirements on a software system are traditionally captured as text that describes the expected functionality in the domain of a real-world system. Natural language processing methods allow us to extract the knowledge from such requirements and transform it, e.g., into a model. Moreover, these methods can improve the quality of the requirements, which usually suffer from ambiguity, incompleteness, and inconsistency. This paper presents a novel approach to using natural language processing. We use the method of grammatical inspection to find specific patterns in the description of functional requirement specifications (written in English). Then, we transform the requirements into a model of Normalized Systems elements. This may realize a possible component of the eagerly awaited text-to-software pipeline. The input of this method is represented by textual requirements. Its output is a running prototype of an information system created using Normalized Systems (NS) techniques. Therefore, the system is ready to accept further enhancements, e.g., custom code fragments, in an evolvable manner ensured by compliance with the NS principles. A demonstration of pipeline implementation is also included in this paper. The text processing part of our pipeline extends the existing pipeline implemented in our system TEMOS, where we propose and implement methods of checking the quality of textual requirements concerning ambiguity, incompleteness, and inconsistency.

Flexible Placements of Graphs with Rotational Symmetry

Authors
Dewar, S.; Grasegger, G.; Legerský, J.
Year
2022
Published
2nd IMA Conference on Mathematics of Robotics. Cham: Springer, 2022. p. 89-97. Springer Proceedings in Advanced Robotics. vol. 21. ISSN 2511-1256. ISBN 978-3-030-91351-9.
Type
Proceedings paper
Annotation
We study the existence of an n-fold rotationally symmetric placement of a symmetric graph in the plane allowing a continuous deformation that preserves the symmetry and the distances between adjacent vertices. We show that such a flexible placement exists if and only if the graph has a NAC-colouring satisfying an additional property on the symmetry; a NAC-colouring is a surjective edge colouring by two colours such that every cycle is either monochromatic, or there are at least two edges of each colour.

Hierarchical Bitmap Indexing for Range Queries on Multidimensional Arrays

Authors
Krčál, L.; Ho, S.-S.; Holub, J.
Year
2022
Published
Database Systems for Advanced Applications. Springer, Cham, 2022. p. 509-525. Lecture Notes in Computer Science. vol. 13245. ISSN 0302-9743. ISBN 978-3-031-00122-2.
Type
Proceedings paper
Annotation
Bitmap indices are widely used in commercial databases for processing complex queries, due to their efficient use of bit-wise operations. Bitmap indices apply natively to relational and linear datasets, with distinct separation of the columns or attributes, but do not perform well on multidimensional array scientific data. We propose a new method for multidimensional array indexing that considers the spatial component of multidimensional arrays. The hierarchical indexing method is based on sparse n-dimensional trees for dimension partitioning, and bitmap indexing with adaptive binning for attribute partitioning. This indexing performs well on range queries involving both dimension and attribute constraints, as it prunes the search space early. Moreover, the indexing is easily extensible to membership queries. The indexing method was implemented on top of a state of the art bitmap indexing library Fastbit, using tables partitioned along any subset of the data dimensions. We show that the hierarchical bitmap index outperforms conventional bitmap indexing, where an auxiliary attribute is required for each dimension. Furthermore, the adaptive binning significantly reduces the amount of bins and therefore memory requirements.

Highways in Warehouse Multi-Agent Path Finding: A Case Study.

Year
2022
Published
Proceedings of the 14th International Conference on Agents and Artificial Intelligence. Madeira: SciTePress, 2022. p. 274-281. ISBN 978-989-758-547-0.
Type
Proceedings paper
Annotation
Orchestrating warehouse sorting robots each transporting a single package from the conveyor belt to its destination is a NP-hard problem, often modeled Multi-agent path-finding (MAPF) where the environment is represented as a graph and robots as agents in vertices of the graph. However, in order to maintain the speed of operations in such a setup, sorting robots must be given a route to follow almost at the moment they obtain the package, so there is no time to perform difficult offline planning. Hence in this work, we are inspired by the approach of enriching conflict-based search (CBS) optimal MAPF algorithm by so-called highways that increase the speed of planning towards on-line operations. We investigate whether adding highways to the underlying graph will be enough to enforce global behaviour of a large number of robots that are controlled locally. If we succeed, the slow global planning step could be omitted without significant loss of performance.

Impact of Clustering on the 8Li β Decay and Recoil Form Factors

Authors
Sargsyan, G.H.; Launey, K.D.; Burkey, M.T.; Gallant, A.T.; Scielzo, N.D.; Savard, G.; Mercenne, A.; Dytrych, T.; Langr, D.; Varriano, L.; Longfellow, B.; Hirsh, T.Y.; Draayer, J.P.
Year
2022
Published
Physical Review Letters. 2022, 128 202503-1-202503-7. ISSN 0031-9007.
Type
Article
Annotation
We place unprecedented constraints on recoil corrections in the β decay of 8Li, by identifying a strong correlation between them and the 8Li ground state quadrupole moment in large-scale ab initio calculations. The results are essential for improving the sensitivity of high-precision experiments that probe the weak interaction theory and test physics beyond the standard model. In addition, our calculations predict a 2+ state of the α+α system that is energetically accessible to β decay but has not been observed in the experimental 8Be energy spectrum, and has an important effect on the recoil corrections and β decay for the A=8 systems. This state and an associated 0+ state are notoriously difficult to model due to their cluster structure and collective correlations, but become feasible for calculations in the ab initio symmetry-adapted no-core shell-model framework.

Improving Classification of Malware Families using a Learned Distance Metric for Low Dimensions

Authors
Year
2022
Published
Sborník příspěvků PAD 2021 Počítačové architektury & diagnostika. Liberec: Technická univerzita v Liberci, 2022. p. 23-26. ISBN 978-80-7494-592-2.
Type
Proceedings paper
Annotation
n this paper, we discuss selected state-of-the-art distance metric learning techniques that have been used for the malware family classification problem, focusing on low-dimensional representations of the input feature space. The goal of distance metric learning algorithms is to find the most suitable distance parameters with respect to a given optimization criterion. In our research, distance metric learning algorithms learn from the metadata contained in the executable file headers in the Portable Executable file format. Several experiments were performed on our dataset with 14,000 samples consisting of six prevalent malware families and benign files. Experimental results have shown that good classification results can be achieved even for two-dimensional symptom vectors.

Improving Document Evolvability based on Normalized Systems Theory

Year
2022
Published
Information Systems and Technologies. Springer, Cham, 2022. p. 131-140. ISSN 2367-3370. ISBN 978-3-031-04818-0.
Type
Proceedings paper
Annotation
During the last decade, there was a huge shift in the problem of evolvability. However, still, the problem remains fully unresolved. Our focus is to improve evolvability in the domain of data stewardship planning. The main problem causing the low evolvability is the use of traditional documents – data management plans. Our approach redesigns the workflow of creating the data management plan with a possibility to extend an application to similar well-structured documents in different domains. We base our approach on principles and recommendations from the Normalized Systems Theory and on the usage of ontologies. The result is a new workflow that should increase the evolvability compared to the current state.

Integer programming in parameterized complexity: Five miniatures

Authors
Gavenčiak, T.; Koutecký, M.; Knop, D.
Year
2022
Published
Discrete Optimization. 2022, 44 ISSN 1572-5286.
Type
Article
Annotation
Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f(k)poly(n). We focus on: • Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. • Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups. • Minding the poly(n): reducing f(k) often has the unintended consequence of increasing poly(n); so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for CAPACITATED DOMINATING SET, SUM COLORING, MAX-q-CUT, and certain other coloring problems by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, indefinite quadratic programs in fixed dimension, parametric integer programs in fixed dimension, and 2-stage stochastic integer programs.

Length-bounded cuts: Proper interval graphs and structural parameters

Authors
Bentert, M.; Heeger, K.; Knop, D.
Year
2022
Published
Journal of Computer and System Sciences. 2022, 126 21-43. ISSN 0022-0000.
Type
Article
Annotation
We study the LENGTH-BOUNDED CUT problem for special graph classes and from a parameterized complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of at most β edges such that each s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [20] conjectured that LENGTH-BOUNDED CUT admits a polynomial-time algorithm if the input graph is a proper interval graph. We confirm this conjecture by providing a dynamic-programming-based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop for LENGTH-BOUNDED CUT parameterized by pathwidth by showing W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that LENGTH-BOUNDED CUT is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.

Migrating Techniques from Search-based Multi-Agent Path Finding Solvers to SAT-based Approach

Authors
Surynek, P.; Stern, R.; Boyarski, E.; Felner, A.
Year
2022
Published
Journal of Artificial Intelligence Research. 2022, 2022(73), 553-618. ISSN 1076-9757.
Type
Article
Annotation
In the multi-agent path finding problem (MAPF) we are given a set of agents each with re- spective start and goal positions. The task is to find paths for all agents while avoiding collisions, aiming to minimize a given objective function. Many MAPF solvers were introduced in the past decade for optimizing two specific objective functions: sum-of-costs and makespan. Two prominent categories of solvers can be distinguished: search-based solvers and compilation-based solvers. Search-based solvers were developed and tested for the sum-of-costs objective, while the most prominent compilation-based solvers that are built around Boolean satisfiability (SAT) were designed for the makespan objective. Very little is known on the performance and relevance of solvers from the compilation-based approach on the sum-of-costs objective. In this paper, we start to close the gap between these cost functions in the compilation-based approach.
Next

Filter

The person responsible for the content of this page: doc. Ing. Štěpán Starosta, Ph.D.