Enhancing Speedup in Network Processing Applications by Exploiting Instruction Reuse with Flow Aggregation

Instruction reuse is a microarchitectural technique that improves the execution time of a program by removing redundant computations at run-time. Although this is the job of an optimizing compiler, they do not succeed many a time due to limited knowledge of run-time data. In this paper we examine instruction reuse of integer ALU and load instructions in network processing applications. Specifically, this paper attempts to answer the following questions: (1) How much of instruction reuse is inherent in network processing applications?, (2) Can reuse be improved by reducing interference in the reuse buffer?, (3) What characteristics of network applications can be exploited to improve reuse?, and (4) What is the effect of reuse on resource contention and memory accesses? We propose an aggregation scheme that combines the high-level concept of network traffic i.e. "flows" with a low level microarchitectural feature of programs i.e. repetition of instructions and data along with an architecture that exploits temporal locality in incoming packet data to improve reuse. We find that for the benchmarks considered, 1% to 50% of instructions are reused while the speedup achieved varies between 1% and 24%. As a side effect, instruction reuse reduces memory traffic and can therefore be considered as a scheme for low power.

Implications of program phase behavior on timing analysis

Knowledge about program worst case execution time (WCET) is essential in validating real-time systems and helps in effective scheduling. One popular approach used in industry is to measure execution time of program components on the target architecture and combine them using static analysis of the program. Measurements need to be taken in the least intrusive way in order to avoid affecting accuracy of estimated WCET. Several programs exhibit phase behavior, wherein program dynamic execution is observed to be composed of phases. Each phase being distinct from the other, exhibits homogeneous behavior with respect to cycles per instruction (CPI), data cache misses etc. In this paper, we show that phase behavior has important implications on timing analysis. We make use of the homogeneity of a phase to reduce instrumentation overhead at the same time ensuring that accuracy of WCET is not largely affected. We propose a model for estimating WCET using static worst case instruction counts of individual phases and a function of measured average CPI. We describe a WCET analyzer built on this model which targets two different architectures. The WCET analyzer is observed to give safe estimates for most benchmarks considered in this paper. The tightness of the WCET estimates are observed to be improved for most benchmarks compared to Chronos, a well known static WCET analyzer.

Relative roles of instruction count and cycles per instruction in WCET estimation

Most of the existing WCET estimation methods directly estimate execution time, ET, in cycles. We propose to study ET as a product of two factors, ET = IC * CPI, where IC is instruction count and CPI is cycles per instruction. Considering directly the estimation of ET may lead to a highly pessimistic estimate since implicitly these methods may be using worst case IC and worst case CPI. We hypothesize that there exists a functional relationship between CPI and IC such that CPI=f(IC). This is ascertained by computing the covariance matrix and studying the scatter plots of CPI versus IC. IC and CPI values are obtained by running benchmarks with a large number of inputs using the cycle accurate architectural simulator, Simplescalar on two different architectures. It is shown that the benchmarks can be grouped into different classes based on the CPI versus IC relationship. For some benchmarks like FFT, FIR etc., both IC and CPI are almost a constant irrespective of the input. There are other benchmarks that exhibit a direct or an inverse relationship between CPI and IC. In such a case, one can predict CPI for a given IC as CPI=f(IC). We derive the theoretical worst case IC for a program, denoted as SWIC, using integer linear programming(ILP) and estimate WCET as SWIC*f(SWIC). However, if CPI decreases sharply with IC then measured maximum cycles is observed to be a better estimate. For certain other benchmarks, it is observed that the CPI versus IC relationship is either random or CPI remains constant with varying IC. In such cases, WCET is estimated as the product of SWIC and measured maximum CPI. It is observed that use of the proposed method results in tighter WCET estimates than Chronos, a static WCET analyzer, for most benchmarks for the two architectures considered in this paper.

Automated Program Recognition

The key to understanding a program is recognizing familiar algorithmic fragments and data structures in it. Automating this recognition process will make it easier to perform many tasks which require program understanding, e.g., maintenance, modification, and debugging. This report describes a recognition system, called the Recognizer, which automatically identifies occurrences of stereotyped computational fragments and data structures in programs. The Recognizer is able to identify these familiar fragments and structures, even though they may be expressed in a wide range of syntactic forms. It does so systematically and efficiently by using a parsing technique. Two important advances have made this possible. The first is a language-independent graphical representation for programs and programming structures which canonicalizes many syntactic features of programs. The second is an efficient graph parsing algorithm.

Elementary Principals' Perceptions of a Leadership Development Training Program

Research indicates that school leaders are crucial to improving instruction and raising student achievement (Council of Chief State School Officers, 2008). As such, educational reforms such as the No Child Left Behind Act (2001) and Race to the Top (2009) have sparked an accountability movement where principals are being held accountable for students' academic achievement and educational outcomes. The shift towards greater accountability has placed new attention on the ways principals are trained. Researchers have noted that organized professional development programs have not adequately prepared school principals to meet the priority demands of the 21st century (Hale & Moorman, 2003; Murphy, 1994). Murphy (1994) stated, "Traditional preparation programs - usually pre-service programs based in colleges or universities, that awarded certification and advanced degrees - rarely concentrated on the leadership challenges that principals actually face in real schools" (p. 4). As a result, many school districts are seeking ways to develop leadership development training programs that will prepare principals for their job responsibilities as a school leader. In spite of the additional training principals receive, researchers suggests that there is an obvious gap between the readiness of administrators to be instructional leaders and the demands for accountability that school administrators face (Hale & Moorman, 2003). This quantitative study examined elementary school principals' perceptions of their leadership development training program. Guided by four research questions, the study examined principals' perceptions of their overall training and how well their training prepared them to deal with school and classroom practices that contribute to student achievement; to work with teachers and others to design and implement a system for continuous student achievement; and to provide necessary support to carry out sound school, curriculum, and instructional practices. Data for this study was collected by way of survey responses from a total of 46 elementary school principals. The results from the study revealed that more than half (58.7%) of participants perceived their training as excellent. While principals' perceived that their training adequately prepared them to work collaboratively in teams, set clear visions and goals, and to use data to improve students achievement, many respondents reported a lack of training in being informed and focused on student achievement. Principals also suggested that they were not effectively trained in finding effective ways to obtain support from central office or community members.

Application-Specific Instruction Set Processor for SoC implementation of Modern Signal Processing Algorithms

A novel application-specific instruction set processor (ASIP) for use in the construction of modern signal processing systems is presented. This is a flexible device that can be used in the construction of array processor systems for the real-time implementation of functions such as singular-value decomposition (SVD) and QR decomposition (QRD), as well as other important matrix computations. It uses a coordinate rotation digital computer (CORDIC) module to perform arithmetic operations and several approaches are adopted to achieve high performance including pipelining of the micro-rotations, the use of parallel instructions and a dual-bus architecture. In addition, a novel method for scale factor correction is presented which only needs to be applied once at the end of the computation. This also reduces computation time and enhances performance. Methods are described which allow this processor to be used in reduced dimension (i.e., folded) array processor structures that allow tradeoffs between hardware and performance. The net result is a flexible matrix computational processing element (PE) whose functionality can be changed under program control for use in a wider range of scenarios than previous work. Details are presented of the results of a design study, which considers the application of this decomposition PE architecture in a combined SVD/QRD system and demonstrates that a combination of high performance and efficient silicon implementation are achievable. © 2005 IEEE.

CORDIC based application-specific instruction set processor for QRD/SVD

An application specific programmable processor (ASIP) suitable for the real-time implementation of matrix computations such as Singular Value and QR Decomposition is presented. The processor incorporates facilities for the issue of parallel instructions and a dual-bus architecture that are designed to achieve high performance. Internally, it uses a CORDIC module to perform arithmetic operations, with pipelining of the internal recursive loop exploited to multiplex the two independent micro-rotations onto a single piece of hardware. The net result is a flexible processing element whose functionality can be changed under program control, which combines high performance with efficient silicon implementation. This is illustrated through the results of a detailed silicon design study and the applications of the techniques to a combined SVD/QRD system.

Exploiting dynamic timing margins in microprocessors for frequency-over-scaling with instruction-based clock adjustment

Static timing analysis provides the basis for setting the clock period of a microprocessor core, based on its worst-case critical path. However, depending on the design, this critical path is not always excited and therefore dynamic timing margins exist that can theoretically be exploited for the benefit of better speed or lower power consumption (through voltage scaling). This paper introduces predictive instruction-based dynamic clock adjustment as a technique to trim dynamic timing margins in pipelined microprocessors. To this end, we exploit the different timing requirements for individual instructions during the dynamically varying program execution flow without the need for complex circuit-level measures to detect and correct timing violations. We provide a design flow to extract the dynamic timing information for the design using post-layout dynamic timing analysis and we integrate the results into a custom cycle-accurate simulator. This simulator allows annotation of individual instructions with their impact on timing (in each pipeline stage) and rapidly derives the overall code execution time for complex benchmarks. The design methodology is illustrated at the microarchitecture level, demonstrating the performance and power gains possible on a 6-stage OpenRISC in-order general purpose processor core in a 28nm CMOS technology. We show that employing instruction-dependent dynamic clock adjustment leads on average to an increase in operating speed by 38% or to a reduction in power consumption by 24%, compared to traditional synchronous clocking, which at all times has to respect the worst-case timing identified through static timing analysis.

An after-school literacy program : investigating the experiences of students with literacy difficulties, their volunteer tutors, and the tutors' transition into the teaching profession

This research responds to a pervasive call for our educational institutions to provide students with literacy skills, and teachers with the instructional supports necessary to facilitate this skill acquisition. Questions were posed to gain information concerning the efficacy ofteaching literacy strategies to students with learning difficulties, the impact of this training on their volunteer tutors, and the influence of this experience on these tutors' ensuing instructional practice as teacher candidates in a preservice education program. Study #1 compared a nontreatment group of students with literacy difficulties who participated in the program and found that program participants were superior at reading letter patterns and at comprehending the elements of story grammar. Concurrently, the second study explored the experiences of 19 volunteer tutors and uncovered that they acquired instructional skills as they established a knowledge base in teaching reading and writing, and they affirmed personal goals to become future teachers. Study #3 tracked 6 volunteer tutors into their pre-service year and identified their constructions, and beliefs about literacy instruction. These teacher candidates discussed how they had intended to teach reading and writing strategies based on their position that effective teaching ofthese skills in the primary grades is integral to academic success. The teacher candidates emphasized the need to build rapport with students, and the need to exercise flexibility in lesson plan delivery while including activities to meet emotional and developmental requirements of students. The teacher candidates entered their pre-service education with an initial cognition set based on the limited teaching context of tutoring. This foundational ii perception represented their prior knowledge of literacy instruction, a perception that appeared untenable once they were immersed in a regular instructional setting. This disparity provoked some of the teacher candidates to denounce their teacher mentors for not consistently employing literacy strategies and individualized instruction. This critical perspective could have been a demonstration of cognitive dissonance. In the end, when the teacher candidates began to look toward the future and how they would manage the demands of an inclusive classroom, they recognized the differences in the contexts. With an appreciation for the need for balance between prior and present knowledge, the teacher candidates remained committed to implementing their tutoring strategies in future teaching positions. This document highlights the need for teacher candidates with instructional experience prior to teacher education, to engage in cognitive negotiations to assimilate newly acquired pedagogies into existing pedagogies.

Evaluating the Norfolk physical education program with respect to fitness-level improvement

The grades seven and eight physical education program of the Norfolk Board of Education was evaluated with respect to fitnesslevel improvement, an objective of the Ministry of Education for the province of Ontario. The Canada Fitness Award battery of fitness tests was used to measure fitness levels. It was established that in September the students were unfit, and in May they were fit. This indicated that the Norfolk physical education program was effective, with respect to the criterion used for this research. In addition, it was discovered that fitness-level improvement was significantly related to certain variables: teacher qualifications, teaching experience, school, and participation in extracurricular physical activity. Considering the results of the research, it was recommended that the Norfolk Board of Education hire young, qualified physical education teachers; create the position of Physical Education Consultant; and strive to create equitable resources for physical education instruction, in order that the school to which a student belongs no longer will be a determinant of fitness improvement.

Explicit versus implicit spelling strategy instruction and its effects on grade one children's invented spellings

The intent of this study was to investigate .the effectiveness of teaching thirty-five Grade One children a variety of effective spelling strategies in comparison to tradit~onal spelling instruction. Strategy instruction included training in phonology, imagery and analogy. In addition, the type of instruction pro~ided (implicit versus explicit) was also examined. Children were seen in small groups of four or five, for four, twenty-five minute sessions. All children were tested prior and immediately following the training sessions, as well as at 14-day follow-ups. Pretest and posttest measures included a dictated spelling test (based on words used in training), a developmental spelling test and a sample of each child's writing. In addition, children completed a metacognitive spelling test as a measure of their strategy awareness. Performance scores on the pretest and posttest measures were compared to determine if any differences existed between the three spelling instruction groups using the Dunn-Bonferroni and Dunnett procedures. Findings revealed that explicit strategy instruction was the most effective spelling program for improving Grade One children's invented spellings. Children who received this instruction were able to spell targeted words more accurately, even after a 14-day follow-up, and were able to recall more effective spelling strategies than children who received either implicit strategy instruction or traditional strategy instruction.

The effectiveness of explicit strategy instruction on the top level structure of a text

Thesis (M.Ed.)-- Brock University, 1995.

The impact of a digital children's literature program on primary students' reading motivation

This qualitative study stemmed from a concern of the perceived decline in students' reading motivation after the early years of schooling, which has been attributed to the disconnect between the media students are accustomed to using outside the classroom and the media they predominantly use within the classroom. This research documented the effectiveness of a digital children's literature program and a postreading multimedia program on eight grade 1 students' reading motivation, word recognition, and comprehension abilities. Eight students were given ten 25-minute sessions with the software program over 15 weeks. Preprogram, interim-program, and postprogram qualitative data were collected from students, teachers, and parents through questionnaires, interviews, standardized reading assessment tools, classroom observations, field notes, and student behaviour observation checklists. Findings are summarized into 3 themes. The motivational aspects and constructivist styles of instruction in the digital reading programs may have contributed to 5 student participants' increased participation in online storybook reading at home. Qualitative data revealed that the digital children's literature program and multimedia postreading activities seemed to have a positive influence on the majority of grade 1 student participants' reading motivation, word recognition, and listening comprehension skills. These findings suggest the promise of multimedia and Internet-based reading software programs in supporting students with reading andlor behavioural difficulties. In keeping with current educational initiatives and efforts, increased use of media literacy practices in the grade 1 curriculum is suggested.

Reading Instruction and Instructors’ Perceptions of Learners’ Needs in LINC Level 1-3 Classes

This study investigates instructors’ perceptions of reading instruction and difficulties among Language Instruction for Newcomers to Canada (LINC) Level 1-3 learners. Statistics Canada reports that 60% of immigrants possess inadequate literacy skills. Newcomers are placed in classes using the Canadian Language Benchmarks but large, mixed-level classes create little opportunity for individualized instruction, leading some clients to demonstrate little change in their reading benchmarks. Data were collected (via demographic questionnaires, semi-structured interviews, teaching plans, and field study notes) to create a case study of five LINC instructors’ perceptions of why some clients do not progress through the LINC reading levels as expected and how their previous experiences relate to those within the LINC program. Qualitative analyses of the data revealed three primary themes: client/instructor background and classroom needs, reading, strategies, methods and challenges, and assessment expectations and progress, each containing a number of subthemes. A comparison between the themes and literature demonstrated six areas for discussion: (a) some clients, specifically refugees, require more time to progress to higher benchmarks; (b) clients’ level of prior education can be indicative of their literacy skills; (c) clients with literacy needs should be separated and placed into literacy-specific classes; (d) evidence-based approaches to reading instruction were not always evident in participants’ responses, demonstrating a lack of knowledge about these approaches; (e) first language literacy influences second language reading acquisition through a transfer of skills; and (f) collaboration in the classroom supports learning by extending clients’ capabilities. These points form the basis of recommendations about how reading instruction might be improved for such clients.