dataesr/scientific-paragraphs-categorization huggingface dataset:
Putting it all together Finally, in Listing 20, we show the code that instantiates the trace through the constructor mkTrace, defines the proven arbitration function TDM_controller, and finally instantiates the controller (using mkController, cf. Listing 12). The (1) ACT date ∶= T RP + 1 CAS date ∶= ACT date + (T RCD + 1) = (T RP + 1) + (T RCD + 1) = 38 SL > CAS date + 1 SL > 39 (2) WCL = (SL -1) + i ⋅ SL ⋅ SN + CAS date = 39 + 1 ⋅ 40 ⋅ 4 + 38 = 237 1 3 Real-Time Systems (2023) 59:664-704 command trace instance is only accepted by Coq if all proofs are provided as arguments to the constructor, which means that the implementation is correct. In the listing, we show that Cmds_T_RRD_ok t and Cmds_T_FAW_ok t are provided as arguments. These are the actual proofs that satisfy the t RRD and t FAW constraints, respectively.
Modelling semantics The expressivity provided by Coq allows us to model other interesting properties about DRAM controllers. Notably, we can write classes that define certain semantics, e. g. , guarantees on the possible order in which requests are handled. To showcase this, we model two flavors of Lamport's definition of Sequential Consistency  Lamport (1979) (SC). According to Lamport, sequential consistency in a multiprocessor system is achieved when two requirements are met: -Requirement R1: Each processor issues memory requests in the order specified by its program. -Requirement R2: Memory requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request into this queue. Requirement R1, on the one hand, is an assumption on the behaviour of processors, and is therefore not modelled from the memory controller's point of view.
Evaluation Table  4  presents the code size and the compilation times for the specification files, both implementations, and the proof scripts. As it can be seen, the implementations themselves are small compared to the specification and the proofs. The proofs are in the order of 10 to 25 times longer than the implementations. 14 As proofs are checked by Coq's kernel, compiling the files containing the proofs also takes more time than files containing simply code. 14 As stated by  Boldo et al. (2017) , Coq proofs are usually as long as paper and pencil proofs, which means that automatising the proof process with Coq is comparable to manual proofs (concerning length). Furthermore, the set of hypothesis used for the proofs form an exploitable mathematical model by itself. This set of hypothesis is made of formulas establishing linear inequalities between the controller parameters and the timing constraints, which can be fed to a Linear Programming (LP) solver in order to obtain optimal values for the controller parameters.
Code generation & simulation External environments/frameworks can interact with our model through calls to the Init and Next functions. Because these functions together define a transition system, which is essential to hardware design, they can be embedded into foreign code, such as software simulators and hardware. To showcase this feature, we choose MCsim  Mirosanlou et al. (2020) , a cycle-accurate DRAM simulator written in C++ to host our proved code. To establish an interface between both, we use Coq's extraction feature, which can output code in different programming languages. We opt for Haskell, since it has a well-documented Foreign Function Interface (FFI) 15  library that allows Haskell programs to cooperate with C/C++ programs  16. We use MCsim's trace reading function to model request arrivals, which fetches a new request after completing the preceding one.
Moreover, the simulator provides a class to implement controllers, which contains a method update, called each clock cycle to update the internal state of the controller. This method makes a call to the requestSchedule method followed by a call to commandSchedule. According to pre-defined arbitration policies, the former fetches requests from the pending queues, generates commands and puts them into a buffer. The latter chooses one of the commands in this buffer and sends it to the device. Since our model performs all of these steps, we replace the calls to requestSchedule and commandSchedule with calls to Init (for the first cycle) and Next. In addition, we encapsulate the generated code inside Haskell wrapper functions to properly handle data on both sides: states are passed back and forth between C++ and Haskell through opaque pointers, and other data structures, such as requests and commands, are converted with the aid of hsc2hs, 17  a preprocessor that helps with writing Haskell bindings to C.
The framework provides a trustworthy design path from end to end. The design flow proposed by the framework is presented through a diagram in Fig. 9. In other words, we claim that the trust in every link in that diagram is increased, compared to other real-time hardware design methodologies. First, consider the link between the JEDEC standards and the Coq-written model (leftmost arrow). The language used to write our specification is very close to the language used in the standard itself, which is a mixture of graphical and natural language. Take, for instance, the listings shown throughout the paper: proof obligations are formulated through propositions written in a mixture of first and higher-order logic and do resemble natural language. It is relatively easy to be convinced that our proof obligations do capture the actual behaviour described in the JEDEC standards.
Other state-of-the-art work that implement some formal approach w. r. t DRAM problem rely on complex mathematical representations to represent the same properties. As comparison, consider the UPPALL finite state-machines proposed by  Li et al. (2016) , used to model the very same properties. While we do not claim that the representation is inherently harder, we do state that there is a larger gap between the languages used in the model and the standard; and this gap can lead to poor modelling. Second, consider the link between specification (model) and implementation/ proofs. From the fact that proofs and programs are essentially the same, many benefits follow: 1. Proofs are machine-checked by Coq's kernel and therefore more trustworthy. 2. Every single hypothesis used for proving obligations must be made explicit and grouped together in classes-which allows better management, since hypotheses are no longer scattered throughout the paper.
3. Proofs are complete, since hand-waving and oversimplifying will not work in Coq. 4. There is no trust gap coming from different representations of model and proofs. In other words, paper-and-pencil mathematical abstractions about models can introduce another language gap and lead to poor modelling. 5. Hardware designs can hide the underlying mathematical formalism of timing analyses from the reader. Differently put, if a new hardware component is introduced within such a framework, the designer can present it without giving details about timing analyses, by just saying that all the proof obligations have been successfully satisfied. Hence, the job of reviewers and readers then switches from checking if paper-and-pencil proofs are correct to merely checking if the properties captured by the specification are correct (which leads us back to the first point).
Conclusion & future work We propose a new way of designing Real-Time Memory Controllers. We write a formal specification that defines the properties of interest as proof obligations. We focus on properties related to the respect of timing constraints, correctness of the command protocol, and assertiveness that every request is handled in bounded time. We refine our specification with two implementations (in which we write proofs for each proof obligation in the specification). We validate our specification through execution on a simulator and compare simulation results with other known controllers. The follow-up to this work consists in using Cava (c. f Sect. 2. 3) to produce HDL code directly from the framework. The generated HDL code will then be used inside of a DDR4 hardware simulation environment.
Results In this paper, we apply the recently-introduced theoretical framework of cherry picking to design a class of efficient heuristics that are guaranteed to produce a network containing each of the input trees, for practical-size datasets consisting of binary trees. Some of the heuristics in this framework are based on the design and training of a machine learning model that captures essential information on the structure of the input trees and guides the algorithms towards better solutions. We also propose simple and fast randomised heuristics that prove to be very effective when run multiple times. Conclusions Unlike the existing exact methods, our heuristics are applicable to datasets of practical size, and the experimental study we conducted on both simulated and real data shows that these solutions are qualitatively good, always within some small constant factor from the optimum.
Proposed algorithms for multiple trees were either completely impractical or ran in reasonable time only for very small numbers of input trees. This situation changed drastically with the introduction of so-called cherry-picking sequences  [2]. This theoretical setup opened the door to solving instances consisting of many input trees like most practical datasets have. Indeed, a recent paper showed that this technique can be used to solve instances with up to 100 input trees to optimality  [3] , although it was restricted to binary trees all having the same leaf set and to so-called "tree-child" networks. Moreover, its running time has a (strong) exponential dependence on the number of reticulate events. In this paper, we show significant progress towards a fully practical method by developing a heuristic framework based on cherry picking comprising very fast randomised heuristics and other slower but more accurate heuristics guided by machine learning.
Experiments The code of all our heuristics and for generating data is written in Python and is available at https:// github. com/estherjulien/learn2cherrypick. All experiments ran on an Intel Xeon Gold 6130 CPU @ 2. 1 GHz with 96 GB RAM. We conducted experiments on both synthetic and real data, comparing the performance of Rand, TrivialRand, ML and Triv-ialML, using threshold τ = 0. Similar to the training data, we generated two synthetic datasets by first growing a binary orchard network N using  [22] , and then extracting T as a subset of the exhaustive trees displayed in N. We provide details on each dataset in Sect. "Experimental results". We start by analysing the usefulness of tree expansion, the heuristic rule described in Sect. "Improving heuristic TrivialRand via tree expansion". We synthetically generated 112 instances for each tree set size |T | ∈ {5, 10, 20, 50, 100} (560 in total), all consisting of trees with 20 leaves each, and grouped them by |T | ; we then ran TrivialRand 200 times (both with and without tree expansion) on each instance, selected the best output for each of them, and finally took the average of these results over each group of instances.
Prediction model The random forest is implemented with Python's scikit-learn  [24]  package using default settings. We evaluated the performance of our trained random forest models on different datasets in a holdout procedure: namely, we removed 10% of the data from each training dataset, trained the models on the remaining 90% and used the holdout 10% for testing. The accuracy was assessed by assigning to each test data point the class with the highest predicted probability and comparing it with the true class. Before training the models, we balanced each dataset so that each class had the same number of representatives. Each training dataset differed in terms of the number M of networks used for generating it and the number of leaves of the networks. For each dataset, the number L of leaves of each generated network was uniformly sampled from [2, max L] , where max L is the maximum num- ber of leaves per network.
We constructed LGT networks using the LGT generator of  [22]. This generator has three parameters: n for the number of steps, α for the proba- bility of lateral gene transfer events, and β for regulating the size of the biconnected components of the network (called blobs). The combination of these parameters determines the level (maximum number of reticulations per blob), the number of reticulations, and the number of leaves of the output network. In our experiments, α was uniformly sampled from [0. 1, 0. 5] and β = 1 (see  [22]  for more details). To generate normal networks we used the same generator with the same parameters, but before adding a reticulation we check if it respects the normality constraints and only add it if it does. Each generated network gave rise to a number of data points: the total number of data points per dataset is shown in Table  3  in Appendix B.
Each row of Table  3  corresponds to a dataset on which the random forest can be trained, obtaining as many ML models. We tested all the models on all the synthetically generated instances: we show these results in Figs. 18 , 19 and 20 in Appendix C. In Sect. "Experimental results" we will report the results obtained for the best-performing model for each type of instance. Among the advantages of using a random forest as a prediction model, there is the ability of computing feature importance, shown in Table  4  in Appendix B. Some of the most useful features for a cherry (x, y) appear to be 'Trivial' (the ratio of the trees containing both leaves x and y in which (x, y) is a cherry) and 'Cherry in tree' (the ratio of trees that contain (x, y)). This was not unexpected, as these features are well-suited to identify trivial cherries.
Experimental results We assessed the performance of our heuristics on instances of four types: normal, LGT, ZODS (binary non-orchard networks), and real data. Normal, LGT and ZODS data are synthetically generated. We generated the normal instances much as we did for the training data: we first grew a normal network using the LGT generator and then extracted all the exhaustive trees displayed in the network. We generated normal data for different combinations of the following parameters: L ∈ {20, 50, 100} (number of leaves per tree) and R ∈ {5, 6, 7} (reticulation number of the original network). Note that, for normal instances, |T | = 2 R. For every combination of the param- eters L and R we generated 48 instances: by instance group we indicate the set of instances generated for one specific parameter pair.
Following  [26]  we set = 1 and we sampled ν ∈ [0. 0001, 0. 4] uniformly at ran- dom. Like for the LGT instances, we generated an instance group of size 48 for each pair of values (L, |T |) and (L, R), with L ∈ {20, 50, 100} , |T | ∈ {20, 50, 100} , R ∈ {10, 20, 30}. Finally, the real-world dataset consists of gene trees on homologous gene sets found in bacterial and archaeal genomes, was originally constructed in  [27]  and made binary in  [3]. We extracted a subset of instances (Table  2 ) from the binary dataset, for every combination of parameters L ∈ {20, 50, 100} and |T | ∈ {10, 20, 50, 100}. For the synthetically generated datasets, we evaluated the performance of each heuristic in terms of the output number of reticulations, comparing it with the number of reticulations of the network N from which we extracted T.
For the normal instances, N is the optimal network [23, Theorem 3. 1]; this is not true, in general, for the LGT and ZODS datasets, but even in these cases, r(N) clearly provides an estimate (from above) of the optimal value, and thus we used it as a reference value for our experimental evaluation. For real data, in the absence of the natural estimate on the optimal number of reticulations provided by the starting network, we evaluated the performance of the heuristics comparing our results with the ones given by the exact algorithms from  [3]  (TreeChild) and from  [7]  (Hybroscale), using the same datasets that were used to test the two methods in  [3]. These datasets consist of rather small instances ( |T | ≤ 8 ); for larger instances, we run TrivialRand 1000 times for each instance group, selected the best result for each group, and used it as a reference value (Fig.
Experiments on LGT data For the experiments on LGT data we used the ML model trained on  1000  LGT networks with at most 100 leaves per network (see Fig. 19  in Appendix C). The setting of the experiments is the same as for the normal data (we run the randomised heuristics multiple times and the machine-learned heuristics only once for each instance), with two important differences. First, for LGT data we only take proper subsets of the exhaustive trees displayed by the generating networks, and thus we have two kinds of instance groups: one where in each group the number of trees extracted from a network and the number of leaves of the networks are fixed, but the trees come from networks with different numbers of reticulations; and one where the number of reticulations of the generating networks and their number of leaves are fixed, but the number of trees extracted from a network varies.
The second important difference is that the reference value we use for LGT networks is not necessarily the optimum, but it is just an upper bound given by the number of reticulations of the generating networks which we expect to be reasonably close to the optimum (see Sect. "Obtaining training data"). The results for the LGT datasets are shown in Fig. 8. Comparing these results with those of Fig. 7 , it is evident that the LGT instances were more difficult than the normal ones for all the tested heuristics: this could be due to the fact that the normal instances consisted of all the exhaustive trees of the generating networks, while the LGT instances only have a subset of them and thus carry less information. The machine-learned heuristics performed substantially better (up to 80% on average) than the best randomised heuristic TrivialRand in all instance groups but the ones with the smallest values for parameters R, |T | and L, for which the performances are essentially overlapping.
Experiments on ZODS data For the experiments on ZODS data we used the ML model trained on  1000  LGT networks with at most 100 leaves per network (see Fig. 20  in Appendix C). The setting of the experiments is the same as for the LGT data, and the results are shown in Fig. 9. At first glance, the performance of the randomised heuristics seems to be better for ZODS data than for LGT data (compare Figs. 8  and 9 ), which sounds counterintuitive. Recall, however, that all the graphs show the ratio between the number of reticulations returned by our methods and a reference value, i. e. , the number of reticulations of the generating network: while we expect this reference to be reasonably close to the optimum for LGT networks, this is not the case for ZODS networks. In fact, a closer look to ZODS networks shows that they have a large number of redundant reticulations which could be removed without changing the set of trees they display, and thus their reticulation number is in general quite larger than the optimum.
The bottom graphs compare the average output of ML within each instance group and the average of the best output given by TrivialRand for each instance group. The shaded areas represent 95% confidence intervals Having a reference value significantly larger than the optimum makes the ratios shown in Fig. 9  small (close to 1, especially for TrivialRand on small instances) without implying that the results for the ZODS data are better than the ones for the LGT data. The graphs of Figs. 8 and 9 are thus not directly comparable. The reference value for the experiments on ZODS data not being realistically close to the optimum, however, does not invalidate their significance. Indeed, the scope of such experiments was just to compare the performance of the machine-learned heuristics on data entirely different from those they were trained on with the performance of the randomised heuristics, which should not depend on the type of network that was used to generate the input.
Experiments on real data We conducted two sets of experiments on real data, using the ML model trained on the dataset trained on 1000 LGT networks with at most 100 leaves each. For sufficiently small instances, we compared the results of our heuristics with the results of two existing tools for reconstructing networks from binary trees: TreeChild  [3]  and Hybroscale  [7]. Hybroscale is an exact method performing an exhaustive search on the networks displaying the input trees, therefore it can only handle reasonably small instances in terms of the number of input trees. TreeChild is a fixed-parameter (in the number of reticulations of the output) exact algorithm that reconstructs the best tree-child network, a restricted class of phylogenetic networks, and due to its fast-growing computation time cannot handle large instances either.
We tested ML and TrivialRand against Hybroscale and TreeChild using the same dataset used in  [3] , in turn taken from  [27]. The dataset consists of ten instances for each possible combination of the parameters |T | ∈  [2, 8]  and L ∈ {10, 20, 30, 40, 50, 60, 80, 100, 150}. In Fig. 10  we show results only for the instance groups for which Hybroscale or TreeChild could output a solution within 1 h, consistent with the experiments in  [3]. As a consequence of Hybroscale and TreeChild being exact methods (TreeChild only for a restricted class of networks), they performed better than both ML and TrivialRand on all instances they could solve, although the best results of TrivialRand are often Fig. 9  Experimental results for ZODS data. Each point on the horizontal axis corresponds to one instance group.
The results are reported in Fig. 11 , and show that the choice of the networks on which we train our model has a big impact on the quality of the results for the real datasets. This is in contrast with what we observed for the synthetic datasets, for which only the class of the training networks was important, not the specific instances of the networks themselves. According to what was noted in  [3] , this is most likely due to the fact that the real phylogenetic data have substantially more structure than random synthetic datasets, and the randomly generated training networks do not always reflect this structure. By chance, the networks we used for training the model we used in  [19]  were similar to real phylogenetic networks, unlike the 1000 networks in the training set of this paper.
Experiments on scalability We conducted experiments to study how the running time of our heuristics scales with increasing instance size for all datasets. In Fig. 12  we report the average of the running times of ML for the instances within each instance group with a 95% confidence interval, for an increasing number of reticulations (synthetic datasets) or number of trees (real dataset). The datasets and the instance groups are those described in the previous sections. Note that we did not report the running times of the randomised heuristics because they are meant to be executed multiple times on each instance, and in all the experiments we bounded the number of executions precisely using the time required for one run of ML. We also compared the running time of our heuristics with the running times of the exact methods Tree-Child and Hybroscale.