{'fraction_non_alphanumeric': 0.026785714285714284, 'fraction_numerical': 0.006152003484320557, 'mean_word_length': 4.763727643551929, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Relationship Detection Measures for Binary SoC Data

System-on-Chip (SoC) designs are used in every aspect of computing and their optimization is a difficult but essential task in today's competitive market. Data taken from SoCs to achieve this is often characterised by very long parallel streams of binary data which have unknown relationships to each other. This paper explains and empirically compares the accuracy of several methods used to detect the existence of these relationships in a wide range of systems. A probabilistic model is used to construct and test a large number of SoC-like systems with known relationships which are compared with the estimated relationships to give accuracy scores. The measures Cov() and Dep() based on covariance and independence are demonstrated to be the most useful, whereas measures based on the Hamming distance and geometric approaches are shown to be less useful for detecting the presence of relationships between SoC data.


Introduction
SoC designs include the processors and associated peripheral blocks of silicon chip based computers and are an intrinsic piece of modern computing, owing their often complex design to lifetimes of work by hundreds of hardware and software engineers. The SoC in a RaspberryPi [11] for example includes 4 ARM processors, memory caches, graphics processors, timers, and all of the associated interconnect components. Measuring, analysing, and understanding the behavior of these systems is important for the optimization of cost, size, power usage, performance, and resiliance to faults.
Sampling the voltage levels of many individual wires is typically infeasible due to bandwidth and storage constraints so sparser event based measurements are often used instead; E.g. Observations like "cache miss @ 123 ns". This gives rise to datasets of very long parallel streams of binary occurrence/non-occurrence data so an understanding of how these measured event streams are related is key to the design optimization process. It is therefore desirable to have an effective measure of the relation between streams to indicate the existance of pairwise relationships. Given that a SoC may perform many different tasks the relationships may change over time which means that a windowed or, more generally, a weighted approach is required. Relationships between event streams are modelled as boolean functions composed of negation (NOT), conjunction (AND), inclusive disjunction (OR), and exclusive disjunction (XOR) operations since this fits well with natural language and has successfully been applied to many different system types [5]; E.g. Relationships of a form like "flush occurs when filled AND read access occur together".
This paper provides the following novel contributions: -A probabilistic model for SoC data which allows a large amount of representative data to be generated and compared on demand. -An empirical study on the accuracy of several weighted correlation and similarity measures in the use of boolean relationship detection.
A collection of previous work is reviewed, and the measures are formally defined with the reasoning behind them. Next, assumptions about the construction of SoC relationships are explained and the design of the experiment is described along with the method of comparison. Finally results are presented as a series of Probability Density Function (PDF) plots and discussed in terms of their application.

Previous Work
An examination of currently available hardware and low-level software profiling methods is given by Lagraa[9] which covers well known techniques such as using counters to generate statistics about both hardware and software events -effectively a low cost data compression. Lagraa's thesis is based on profiling SoCs created specifically on Xilinx MP-SoC devices, which although powerful, ensures it may not be applied to data from other sources, such as in post-silicon. Lo et al [10] described a system for describing behaviour with a series of statements using a search space exploration process based on boolean set theory. While this work has a similar goal of finding temporal dependencies it is acknowledged that the mining method does not perform adequately for the very long traces often found in real-world SoC data. Ivanovic et al [7] review time series analysis models and methods where characteristic features of economic time series are described such as high auto-dependence and inter-dependence, high correlation, non-stationarity, and drawn from noisy sources. SoC data is expected to have these same features, together with full binarization and much greater length. The expected utility approach to learning probabilistic models by Friedman and Sandow [3] minimises the Kullbach-Leibler distance between observed data and a model which is attemping to fit that data which is an iterative method. As noted in Friston et al [4] fully learning all parameters of a Bayesian network through empirical observations is an intractable analytic problem which simpler noniterative measures can only roughly approximate. The approach of modelling relationships as boolean functions has been used for measuring complexity and pattern detection in a variety of fields including complex biological systems from the scale of proteins to groups of animals [17]. 'Correlation' is a vague term which has several possible interpretations [15] including treating data as high dimensional vectors, sets, and population samples. A wide survey of binary similarity and distance measures by Choi et al [1] tabulates 76 methods from various fields and classify them as either distance, non-correlation, or correlation based. A similarity measure is one where a higher result is produced for more similar data, whereas a distance measure will give a higher results for data which are further apart, i.e, less similar. The distinction between correlation and similarity can be shown with an example: If it is noticed over a large number of parties that the pattern of attendence between Alice and Bob is similar then it may be inferred that there is some kind of relationship connecting them. In this case the attendence patterns of Alice and Bob are both similar and correlated. However, if Bob is secretly also seeing Eve it would be noticed that Bob only attends parties if either Alice or Eve attend, but not both at the same time. In this case Bob's pattern of attendence may not be similar to that of either Alice or Eve, but will be correlated with both. It can therefore be seen that correlation is a more powerful approach for detecting relationships, although typically involves more calculation.

Measures
A measured stream of events is written as f i where i is an identifier for one particular event source such as cache miss. Where f i (t) = 1 indicates event i was observed at time t, and f i (t) = 0 indicating i was not observed at time t. A windowing or weighting function w is used to create a weighted average of each measurement to give an expectation of an event occurrence.
Bayes theorem may be rearranged to find the conditional expectation.
It is not sufficient to look only at conditional expectation to determine if X and Y are related. For example, the result Pr(X|Y ) = 0.9 may arise from X's relationship with Y , but may equally arise from the case Pr(X) = 0.9. An intuitive approach might be to measure how similar a pair of event streams are. The expected number of different bits between two binary measurements E[|X − Y |] is the normalised Hamming distance [6]. For the typical set [12] this is equivalent to |E[X] − E[Y ]|. The absolute difference |X − Y | may also be performed with an XOR operation.
The dot in the notation is used to show that this measure is similar to, but not necessarily equivalent to the standard definition. Modifications to the standard definitions may include disallowing NaN, restricting or expanding the range to [0, 1], or reflecting the result. For example, by reflecting the result ofḢam a measure is given where 0 indicates fully different and 1 indicates exactly the same.
A similar approach is to treat a pair of measured event streams as a pair of sets. The Jaccard index first described for comparing the distribution of alpine flora [8], and later refined for use in general sets is defined as the ratio of size the intersection to the size of the union. Tanimoto's reformulation [16] of the Jaccard index shown in Equation (5) was given for measuring the similarity of binary sets.
Treating measurements as points in bounded high dimensional space allows the Euclidean distance to be calculated, reflected and normalized to [0, 1] to show closeness rather than distance. This approach is common for problems where the alignment of objects is to be determined such as facial detection and gene sequencing [2].Ċ It can be seen that this formulation is similar to using the Hamming distance, albeit growing quadratically rather than linearly as the number of identical bits increases. Another geometric approach is to treat a pair of measurements as bounded high dimensional vectors and measure the angle between between them using the cosine similarity as is often used in natural language processing [13] and data mining [14].
The definition ofĊos sets negative similarity results to 0 which effectively ignores anti-relationships. By applying the same correlation measures to the event streams and to reflections of the event streams, anti-relationships will also be found. This allows the negation part of all boolean operations to be discarded without loss of information as the information is simply in a different form; I.e. relationships take the form "idle occurs when NOT busy". The above measures attempt to uncover relationships by finding pairs of events streams which are similar to each other. These may be useful for simple relationships of forms similar to "X leads to Y" but may not be useful for finding relationships which incorporate multiple measurements via a function of boolean operations such as "A AND B XOR C leads to Y". Treating measurement data as samples from a population invites the use of covariance or the Pearson correlation coefficient as a distance measure. Noting that covariance as shown in Equation (10) between two bounded value populations is bounded allowsĊov measure to be defined, again setting negative correlations to 0. For binary measurements with equal weightsĊov can be shown to be equivalent to the Pearson correlation coefficient.
Using this definition it can be seen that if two random variables are independent thenĊov(X, Y ) = 0, however the reverse is not true in general as the covariance of two dependent random variables may be 0. The definition of independence in Equation (13) may be used to get a measure of dependence.
X ⊥ ⊥ Y ⇐⇒ Pr(X) = Pr(X|Y ) The measures defined aboveḢam,Ṫmt,Ċls,Ċos,Ċov, andḊep all share the same codomain [0, 1] where 1 means the strongest relationship. In order to compare these correlation measures an experiment has been devised to quantify their effectiveness.

Experimental Procedure
This experiment constructs a large number of SoC-like systems according to a probabilistic structure and records event-like data from them. The topology of each system is fixed which means relationships between event streams in each system are known in advance of any measuring. The measures above are then applied to the recorded data and compared to the known relationships which allows the effectiveness of each measure to be demonstrated empirically. The maximum number of event streams 2n maxm is set to 100 control the size of the systems and keep them within a reasonable size. Each system is composed of a number of measurement nodes e i∈ [1,m] such that m = m src + m dst of either type 'src' or 'dst' arranged in a bipartite graph as shown in Fig. 1. In each system the numbers of measurement nodes are chosen at random m src , m dst ∼ U(1, n maxm ). Src nodes are binary random variables with a fixed densitity ∼ Arcsin (0, 1) where the approximately equal number of high and low density event streams represents equal importance of detecting relationships and antirelationships. The value of each dst node is formed by combining a number of edges ∼ Lognormal(0, 1) from src nodes. There are five types of systems which relate to the method by which src nodes are combined to produce the value at a dst node; One fifth of systems use only AND operations (∧) to combine connections to each dst node, another fifth uses only OR (∨), and another fifth uses only XOR (⊕). The fourth type of system uniformly chooses one of the ∧, ∨, ⊕ methods to give a mix of homogeneous functions for each dst node. The fifth type gets the values of each dst node by applying chains of operations ∼ U({∧, ∨, ⊕}) combine connections, implemented as Left Hand Associative (LHA). By keeping different connection strategies separate it is easier to see how the measures compare for different types of measuruement relationships.
The known relationships were used to construct an adjacency matrix where K ij = 1 indicates that node i is connected to node j, with 0 otherwise. The di-agonal is not used as these tautological relationships will provide a perfect score with every measure without providing any new information about the measure's accuracy or effectiveness. Each measure is applied to every pair of nodes to construct an estimated adjacency matrix E. Each element E ij is compared with K ij to give an amount of 'True-Positive' and 'False-Negative' where K ij = 1 or an amount of 'True-Negative' and 'False-Positive' where K ij = 0. For example if a connection is known to exist (K ij = 1) and the measure gave a value of 0.7 then the True-Positive and False-Negative values would be 0.7 and 0.3 respectively, with both True-Negative and False-Positive equal to 0. Alternatively if a connection is know to not exist (K ij = 0) then True-Negative and False-Positive would be 0.3 and 0.7, with True-Positive and False-Negative equal to 0. These are used to give scores for the positive, negative, and overall accuracy.
Accuracy Positive = TP TP + FP Accuracy Negative = TN TN + FN Accuracy Overall = TP + TN TP + FN + TN + FP For a measure to be considered useful for detecting connections in these SoC-like systems both Accuracy Positive and Accuracy Negative must be greater than 0, and Accuracy Overall must be greater than 0.5.
In order to generate a useful amount of data 1000 systems were generated, with 10000 samples of each node taken from each. This procedure was repeated for each measure for each system and the PDF of each measure's accuracy is plotted using Kernel Density Estimation (KDE) to see an overview of how well each measure performs over a large number of different systems.

Results and Discussion
The PDF plots are shown in Fig. 2 where more weight on the right hand side towards 1.0 indicates a better measure.
The middle and right columns show the accuracies of positive (meaning "a connection exists") and negative (meaning "a connection does not exist") respectively. It can be seen that all measures score highly for measuring negatives; I.e. when a connection does not exist they give a result close to 0. On its own this does not carry much meaning as a constant 0 will always give a fully accurate answer, Similarly, a constant 1 will give a fully accurate answer for positive links so the plots in the middle and right columns must be considered together with the overall accuracy to judge the usefulness of a measure. Most measures can be seen in the middle column to detect connections much worse than non-connections which indicates that the measures produce conservative results, not generally overestimating the existance of connections. The effect of such high scores for measuring negatives is that the plots for Accuracy Overall are essentially the same as (Accuracy Positive + 1)/2. If instead there were more connections to each dst node, i.e. K was more dense, then the proportion of accurate negative results would be expected to fall and the shape of Accuracy Overall would be altered.
The overall results indicate thatḢam andĊls are close to useless for detecting connections with the majority of their Accuracy Overall scores being around 0.5. It is noteworthy thatṪmt andĊos which are related toḢam andĊls respectively in their approaches perform much better. A characteristic feature employed by bothṪmt andĊos is the convolution f x * f y , whereasḢam andĊls employ an absolute difference |f x − f y |. The best performing measuresĊov andḊep have consistently higher accuracy scores and employ both the convolution, and the product of expectations Each row shows shows plots which are different, although the general picture looks roughly the same. This means that there does not appear to be a measure which suits only a small number of system types, so the best measures may be used for all systems. The fourth and fifth rows (Fig. 2j thru 2o) for homogeneous and LHA functions, and the average of all system types produce very similar plots. This indicates that SoC-like systems may be approximated accurately by the fourth and fifth types.

Conclusion
The formulation and rational behind six methods of measuring similarity or correlation to detect relationships has been given for weighted binary data. The given formulations may also be applied more generally to bounded data in the range [0, 1], though this is not explored in this paper and may be the subject of future work. Other directions of future work include testing more measures or designing specialized measures for SoC relationships.
The measuresĊov andḊep are shown to consistently detect relationships in SoC-like data with higher accuracy than the other measures. This result gives confidence that detection systems may employ these approaches in order to make meaningful gains in the process of optimizing SoC behavior. By using more accurate measures unknown relationships can be uncovered giving SoC developers the information they need to optimize their designs and sharpen their competative edge.    2: KDE plots of accuracy PDF by system type. More weight on the right hand side is always better. X-axis is accuracy from 0 (never correct) to 1 (always correct). Y-axis is probability density that the measure will have that accuracy (unitless).