Mika Gabel
email: mikag@afeka.ac.il

Tommy Dreyfus
email: tommyd@post.tau.ac.il

To whom do we speak when we teach proofs?

Keywords: Proof teaching, flow of proof, Perelman's New Rhetoric, mathematical argumentation

We assess rhetorical aspects of the flow of proof, a notion that encapsulates various aspects of classroom presentation of proof, proposing Perelman's New Rhetoric (PNR) as a theoretical framework. We present findings from semi-structured interviews conducted with experienced mathematics lecturers, who were asked to reflect about general features and pedagogical considerations of mathematical proofs by relating to two proofs of the 'Two Pancakes theorem'. We focus on PNR's concept of audience and argue that lecturers generally address two types of audience, particular and universal, when teaching proofs and need to balance between the requirements of each audience. We conclude that PNR is suitable to capture this inherent tension in teaching proofs.

Reconnecting mathematics and rhetoric

The notion 'flow of a proof' has been used by [START_REF] Gabel | Affecting the flow of a proof by creating presencea case study in Number Theory[END_REF] to examine different aspects of classroom presentation of proof: the way that the lecturer chooses to present the logical structure of the proof, to incorporate informal features into the presentation and to account for various mathematical and instructional contextual factors. The analysis of the informal and contextual features requires a theoretical lens that can account for rhetorical features of the presentation. However, traditionally, scholars perceive rhetoric and mathematics as antithetical disciplines [START_REF] Reyes | Stranger relations: The case for rebuilding commonplaces between rhetoric and mathematics[END_REF], two banks of a river. On one bank -mathematics, dealing with the establishment of unequivocal truths based on the rigorous laws of formal logic, and on the other bank -rhetoric, mostly related to the study of style, expression and ornamental aspects of discourse.

Yet, scholars have been gradually building bridges between the two banks by using rhetorical concepts to gain better understanding of mathematics and mathematical education. [START_REF] Davis | Rhetoric and Mathematics[END_REF], for example, challenged the then prevailing opinion that "mathematical truth is established by a unique mode of argumentation, which consists of passing from hypothesis to conclusion by means of a sequence of small logical steps, each of which is in principle mechanizable..." (pp. 59-60) and claimed that "mathematical proof has its rhetorical moments and its rhetorical elements" (p. 60). [START_REF] Ernest | Forms of knowledge in mathematics and mathematics education: Philosophical and rhetorical perspectives[END_REF] related to other scholars who share that approach and stated that in education this approach is less controversial than in mathematical and philosophical circles. [START_REF] Reyes | Stranger relations: The case for rebuilding commonplaces between rhetoric and mathematics[END_REF] adds that mathematics, as a practice of writing, thinking, and arguing, should be studied by rhetorical scholars, and that rhetorical scholars should explore mathematics discourse as its importance is constantly increasing. In this work, we analyse rhetorical features of mathematical proof presentation through the lens of an argumentation theory called 'The New Rhetoric' (PNR, [START_REF] Perelman | The new rhetoric: A treatise on argumentation[END_REF]. PNR is a comprehensive theory that allows the considerations of a varied range of argument aspects within a single unifying theory and ties these different aspects to the adaptability to the audience for whom the argumentation is intended.

Therefore, it enabled us to relate to different aspects of the flow as well as to the ways these aspects are intertwined.

Perelman's new rhetoric (PNR)

PNR assumes a speaker addressing an audience and studies techniques that aim to increase audience adherence to the theses presented by the speaker. It concerns the effective use of informal reasoning, i.e. reasoning that promotes audience adherence. PNR was initially designed to complement formal logic and to show how choices, decisions, and actions can be justified on rational grounds; thus, it relates to dialectical, rhetorical and contextual features. It asserts that form is subordinated to content and to the effort to persuade, and that reducing an argument to its formal features undermines the rhetoric features that support its meaning. PNR offers a description of various aspects of argumentation: (i) scope and organization, which is a result of the lecturer's need to take into account a complicated, at times contradictory, set of considerations in the proof presentation; (ii) the constitution of a shared basis of agreement between the speaker and the audience (iii) the manner by which the lecturer uses rhetorical figures to endow elements with presence and to focus audience's attention on them; and (iv) different argumentation techniques. Moreover, PNR stresses that an effective argument must be adapted to the audience. In [START_REF] Gabel | Affecting the flow of a proof by creating presencea case study in Number Theory[END_REF] we explained our adaptation of PNR for analysing mathematical proof teaching and how we use PNR to account for different aspects of the flow of a proof; we also discussed aspects (i) and (iii). In the current paper, we focus on PNR's notion of audience and examine its relation to inherent tensions in the teaching of mathematical proofs.

The universal audience and the particular audience in Perelman's new rhetoric (PNR)

The audience plays a pivotal role in PNR. [START_REF] Perelman | The new rhetoric: A treatise on argumentation[END_REF] make a distinction between argumentation aimed to persuade the particular audience addressed by the speaker, which is the actual, physical audience (and therefore the argumentation needs to be adjusted to particular knowledge, experiences, expectations, opinions and norms), and argumentation that transcends particularity and is aimed to convince what is called a universal audience. The universal audience is a mental construct of the speaker, composed of all normally reasonable and competent people, where competence is specific to a discipline or culture, and consists of a series of beliefs, agreements and language that are typical for this discipline, whether it is of scientific, juridical or other nature. Such agreements may be the result of certain conventions that characterize audiences, usually distinguishable by their use of a technical language of their own [START_REF] Van Eemeren | The new rhetoric[END_REF]. While every argument is directed to a specific individual or group, the speaker decides what information and approaches will be convincing according to the universal audience that s/he has in mind. Thus, some arguments appeal only to particular groups in a particular context and some arguments attempt to have a broader appeal. By addressing differences between universal and particular audiences, Perelman believes he can better distinguish between a merely effective argumentation that persuades a particular audience, and a genuinely valid argumentation that convinces the universal audience. In that sense, a universal audience may be used as a standard of relevance [START_REF] Crosswhite | Universality in Rhetoric: Perelman's Universal Audience[END_REF].

Rationale and goals

This work is situated within the growing research field concerned with different styles that mathematical lecturers employ (e.g., [START_REF] Hemmi | Three styles characterising mathematicians' pedagogical perspectives on proof[END_REF][START_REF] Hemmi | Three styles characterising mathematicians' pedagogical perspectives on proof[END_REF] and the various pedagogical considerations they apply while teaching proof (e.g., [START_REF] Dawkins | Values and norms of proof for mathematicians and students[END_REF][START_REF] Lai | Factors mathematicians profess to consider when presenting pedagogical proofs[END_REF].

The goals of this paper are firstly to present different pedagogical dilemmas that mathematicians have when teaching proof at the undergraduate level and secondly to demonstrate how these dilemmas can be interpreted by using PNR's notion of two audiences. We show how the tension between the universal and particular audiences can explain decisions taken by mathematics lecturers and focus on conflicts that emerge during proof teaching between the lecturers' own views of mathematics and the characteristics of their students.

Method

We present findings from interviews conducted with five experienced mathematics lecturers (10-40 years of experience), teaching a variety of tertiary level mathematics courses to diverse student populations (engineering students in college or university, mathematics students, prospective teachers, computer science students, high-school students). They volunteered to be interviewed and were asked about features of mathematical proofs and considerations for proof teaching by relating to the 'Two Pancakes theorem' and its two proofs [START_REF] Davis | The mathematical experience[END_REF]) outlined below: Theorem: Given two arbitrary closed and bounded areas in the plane, A and B, there exists a line that simultaneously bisects the two areas.

Proof 1 uses an arbitrary point O and a directed line l rotating through O (Figure 1); one defines functions p(θ), q(θ): the coordinates on l of the lines perpendicular to l that bisect areas A, B. If r(θ)=p(θ)-q(θ) is positive for some θ, then it is negative for θ+180°. Hence, there exists θ 0 for which r(θ 0 )=0, i.e. p(θ 0 )=q(θ 0 ), according to the intermediate value theorem (IVT). Proof 2 is based on five successively more general cases. Cases 1-2 are trivial: If A and B are circles (concentric in Case 1, non-concentric in Case 2) then the line through their centres bisects both. Case 3 (Figure 1): A is a circle, B does not overlap A; when rotating the diameter of A, the part of the area of B that lies on one side of the diameter, p(θ), changes from 0 to 1; the existence of θ 0 for which p(θ 0 )=0.5 follows from the IVT. Case 4 (Figure 1): A is a circle and B partially overlaps A; now p(0°)+p(180°)=1, and the claim follows from the IVT on 0°≤ θ ≤180°. Case 5: Two arbitrary areas; the same argument as in Case 4 applies with the diameter of A replaced by a line that halves the area of A.

The interviews were semi-structured. Most questions related to features of mathematical proofs in general and pedagogical considerations for teaching proof. The interview began with questions relating to the proofs of the above theorem and proceeded to more general questions. The interviews were audio-recorded, transcribed and analysed using principles of verbal analysis [START_REF] Chi | Quantifying Qualitative Analyses of Verbal Data: A Practical Guide[END_REF]. The analysis was carried out in five steps: (1) Segmenting and reducing: Segmenting the transcriptions into modules that contain an answer to a specific question. Each module was reduced by selecting significant utterances; (2) Coding and organizing: Most categories were created naturally by the interview questions and some were created when reading the reduced data. The relevant utterances were summarized and placed in the appropriate category; (3) Operationalizing evidence: A collection of utterances that constitute evidence for each category was created; (4) Seeking for patterns in the organized data. When such patterns emerged, they were validated by looking for further evidence; (5) Repeating the procedure in order to verify the coding and alter it if necessary.

In this paper, we focus on the lecturer's answers to the following three questions:

1. Which of the two proofs would you use for teaching this theorem, and why? 2. What aspects of the proof do you emphasize when teaching a proof? 3. What language (formal/informal) do you use when teaching a proof?

Findings

We start by presenting the interviewees' answers to the first question: which of the two proofs they would teach and why. Proof 1 was chosen by three interviewees: Sally, Dana and Max. Max claimed that Proof 1 is more correct and properly built: "[it] is built as a proof: you start at the beginning and reach the end. [In Proof 2] I am told: take a case and prove it... What would happen if there were 79 cases?! … It's more elegant to find one proof that does not require the separation into cases"; he also stated that "students should learn the proper way to prove claims" and that the many cases of Proof 2 might "drive the student crazy". Dana stated that the division into cases makes "Proof 2 hard to remember" and Sally stated that it worries her: "…I am always concerned that a case is missing, it's stressful...". Proof 2 was chosen by Tara and Anne who stated that it is more intuitive and less 'tricky'. Tara said: "I relate better to the idea of halving the first domain and then the second one, than to the idea of the perpendicular lines". Anne said that "it enables to teach students how to 'play'" and that the gradual increase in complexity allows students to fully understand each case before proceeding.

The lecturers also suggested how to improve the proofs. Sally, Dana and Max preferred teaching Proof 1 but were aware of its difficulties, mainly the 'Deus ex Machina' nature of the function r(θ). Sally suggested to "divide the board, write down the stages and finally … fill in the details. First the 'how' then … the 'what'… define a-priori where [you are] heading", because "…completing the details is [only] half of the work…". Max suggested using Cases 1-2 of Proof 2 to increase students' intuition regarding the meaning of the claim. Dana suggested emphasizing one central idea: the construction of the distances. These lecturers chose Proof 1 because it agrees with their beliefs about what a "good, proper mathematical proof" is, but contemplated how to improve its communication to their students. Tara and Anne preferred teaching Proof 2; they felt its intuitive nature is better adapted to their students. The division into cases, a disadvantage for others, is an advantage for Anne, who believes that the gradual increase in complexity improves students' learning experience. Tara said that Proof 2 is more intuitive to her than the perpendicular lines of Proof 1; She said: "…I don't like it when proofs are based on an idea that I would not spontaneously think about… if it can be done… without 'tricks', I prefer it". Yet she suggested shortening the proof by omitting Cases 1-2.

Although these findings indicate different lecturer choices, there were noticeable commonalities in their answers. Firstly, Tara and Max chose different proofs, but were both bothered with the imprecise way of using the IVT and stated that one should explicitly define functions and justify their continuity before applying the IVT. For them, some standard of mathematical rigor is important. Secondly, several lecturers refer to meta-proof issues. For example, Sally refers to a proof plan, Anne to pre-proof activities ('play') and Max to the pedagogical value of using precise language. Thirdly, the lecturers address affective aspects, and subjectivity is demonstrated by the opposite attributes that different lecturers relate to the same proof feature. Whereas Sally and Max feel that the division into cases might disturb the students, Anne sees the gradual increase in complexity as giving students a sense of understanding and stability. Thus, the lecturers' choice of proof is highly influenced by their perception of the students attending the lesson. Moreover, earlier in the interview, when asked about their proof preference some lecturers stated that the choice mostly depends on the intended audience. Sally, for example, stated that Proof 1 is clearer in her opinion but that Proof 2 is better for her students. Then, when asked to choose which proof to teach she chose Proof 1 and described pedagogical ways to improve its presentation. The choice of proof appears to be an amalgam of mathematical and pedagogical considerations, personal preferences and convictions.

In the second question, the interviewees were asked what aspects they emphasize while teaching proofs. They all stated that their answer is population dependent. Table 1 summarizes their answers and reveals that lecturers invest a lot of effort in communicating the proof, and raising students' awareness of meta-proof and rhetorical aspects (e.g., aesthetics, and significance). Tara tries "…to look for… the significance, why this conclusion… [and] the way [it] was derived is important…". Anne focuses on pre-proof activities and states that she partly "… wants to teach them how to transform a 'game' into a proof…how to produce… the simplest example that still maintains the features of a problem, … [how] to try to prove or refute when you still don't have a clue if the claim is true or false…". Max adds that his verbal explanations are what "really explains it to students".

Highlighted aspects

Suppressed aspects 1. Ideas that are:

(i) repeated in future proofs or (ii) related to the current content {A, S, D} 2. The thoughts and intuitions that led to the proof {M} 3. In the third question, four were explicitly asked about their use of formal language (the fifth interviewee referred to the use of formal language throughout the interview). Sally used an analogy to explain the importance of using formal language: "… lawyers use words that have meaning only in the context of the law discipline. It's not the same meaning as their dictionary definition…" She says that similarly, students should master the proper way of writing proofs, using the necessary symbols and language. Tara and Anne demonstrate flexibility regarding the use of formality in places where it might obstruct student's learning. For example, Tara states: "in one classroom I might describe the concept of a limit very informally… as a sequence of values getting nearer some value; in a different classroom, I have to use the epsilon-delta definition with extreme formality". Anne admits that "…somewhat reducing the formality" might harm students' understanding but supports her choice by stating that otherwise students may "… lose their grasp of 'the whole'… they need to deal with parts… [and] sub-parts that are not well constructed yet…" Dana's approach marks the other end of the range, for she speaks of 'gluing' things in a non-formal way and clearly expresses her preference to emphasize central ideas rather than to dwell on technical steps. Dana advises students to concentrate on the main, less technical, proof ideas. Thus, the lecturers' answers to the third question reflect a range of attitudes: from a strict use of formal language, via compromises between formality and audience, to an entirely context dependent attitude. They balance between helping the students to be sufficiently acquainted with the customary mathematical language on one hand, and not getting lost in the rigidness and details of extreme formality on the other hand. At the same time, the proof presented to the students should reasonably satisfy some standard of the mathematical community, the same way a legal document should accept approval of law experts.

To summarize, the interviewees discussed a rich collection of proof features, constantly referring to pedagogical considerations. Two themes, subjectivity and context-dependent value of proof features, particularly the type of student population, were prominent throughout the interview.

Discussion of the findings within PNR framework

The findings show that the interviewed lecturers have a clear vision of different mathematical ideas and features of the two proofs, combined with a rich collection of pedagogical considerations. These findings are consistent with the literature (e.g., [START_REF] Hemmi | Three styles characterising mathematicians' pedagogical perspectives on proof[END_REF][START_REF] Lai | Factors mathematicians profess to consider when presenting pedagogical proofs[END_REF]. However, we wish to focus on the manner in which the lecturers consider their students, i.e. the audience, while teaching proofs. [START_REF] Lai | Factors mathematicians profess to consider when presenting pedagogical proofs[END_REF] explored factors that mathematicians claim to consider when preparing a pedagogical proof and found that audience diversity influenced mathematicians in four aspects: (a) the assumed previous knowledge; (b) the actions that need to be taken to avoid potential student difficulties; (c) using techniques students find familiar or comfortable; (d) what mathematical ideas are emphasized by the proof. Indeed, most of these issues were also raised by our interviewees.

Our data show that when mathematicians teach proofs a tension between two poles arises: the first pole is the wish to present the proofs in a rigorous manner acceptable to professional mathematicians (as Max said "the proper way to prove"); the second pole is the wish to accommodate students' cognitive and affective needs so that they will gain adequate understanding and a rewarding learning experience. This tension is widely found in the literature (e.g., [START_REF] Dawkins | Values and norms of proof for mathematicians and students[END_REF][START_REF] Lai | Factors mathematicians profess to consider when presenting pedagogical proofs[END_REF]. [START_REF] Dawkins | Values and norms of proof for mathematicians and students[END_REF], for example, investigate values and norms of mathematicians regarding proof and acknowledge that sometimes the needs of the mathematical community differ from those of the classroom community, which cannot perfectly mimic practices of professional mathematicians. They claim that expecting students to adopt mathematicians' proof norms without perceiving the underlining values might cause a dissonance between the mathematicians' and the students' communication culture. They also state that one outcome is that "researchers... have sensibly advocated loosening various norms for the purpose of encouraging students' genuine insights" (p. 133). Within PNR, this dilemma is an inherent feature of simultaneously addressing the universal and particular audiences. It is not about "compromising" but about adjusting the argument and creating a shared basis of agreement with the students while maintaining a proof presentation that would still be acceptable by professional mathematicians (possibly imagined as sitting at the back of the class). Moreover, PNR not only relates to the difference between the lecturer's and the students' norms and values but also to other rhetorical and informal features of the proof classroom presentation [START_REF] Gabel | Affecting the flow of a proof by creating presencea case study in Number Theory[END_REF], as well as to other types of lecturer-student gaps in the argumentation and their sources.

This may also explain why during the interview, the lecturers frequently answered interview questions focused on mathematical proofs in general by raising pedagogical considerations related to the particular audience, constantly shifting between two perspectives: mathematician and teacher. We give three examples. Sally stated that that as a mathematician, she prefers Proof 1, but Proof 2 better fits her students. Nevertheless, when asked to choose a proof to teach she chose Proof 1, suggesting pedagogical ways to improve its presentation. Sally also stressed the importance of formal language in class, but admitted skipping repetitive stages of proofs, and suppressing details that might currently be too difficult for her students. A similar tension can be found in the suggestion Max made regarding the improvement of Proof 1. Max declared the importance of proof formality and preciseness and chose Proof 1 both as his personal preference and as the better proof to teach. However, he suggested improving the presentation of Proof 1 by adding Cases 1-2 of Proof 2, in order to enhance students' intuition regarding the claim's meaning. A similar tension appeared when Anne, who chose to teach Proof 2 for the feeling of understanding it provides referred to formal language by saying that "…one can skip formality if one has the ability to reconstruct it … but [students] don't know how to do that, so it's a kind of 'pretence' understanding".

Mathematics lecturers address two audiences when teaching proofs: particular and universal. The particular audience is the actual group of students attending the lesson, who bring with them their previous knowledge, attitudes, learning habits, beliefs and cultural conventions. The lecturer needs to address the needs of the particular audience, to maintain a shared basis of agreement with the students and persuade them that the claim was truly proved. In parallel, the lecturer needs to convince the universal audience, which is a mental construct of the lecturer; it may include professional mathematicians, experts of the taught material or admired lecturers. Convincing the universal audience requires different standards of formality, preciseness and rigor. Whenever mathematics lecturers teach proofs, they need to balance between the different requirements of both audiences. The need for this balance is demonstrated, for example, by Dana, who admits that in class she prefers to emphasize important ideas rather than to dwell on technical steps "in an attempt not to give up on classroom proving altogether because then understanding drops to a very low level".

Thus, PNR is a unifying and comprehensive theoretical framework that can be used to interpret a major challenge of proof teaching. Within PNR this challenge is considered an inherent tension that always exists between the need to present a proof that is convincing to the universal audience, in our context a complete, flawless proof accepted by expert mathematicians, and between the need to persuade the particular audience, in our context the students actually attending class. PNR also relates to other rhetorical and informal features of classroom presentation of proof, such as means to endow proof elements with presence [START_REF] Gabel | Affecting the flow of a proof by creating presencea case study in Number Theory[END_REF] as well as to lecturer-student gaps in the argumentation and their sources. Therefore, PNR may be used not only to describe mathematicians' proof presentations but also to evaluate the presentations and to provide practical suggestions of how to improve them.

Figure 1 :

 1 Figure 1: Drawings for Proof 1 and Proof 2 (Case 3, Case 4)

Table 1 : Proof features that are highlighted or suppressed while teaching

 1

		1. Repetitive stages that do not
		contain new ideas or new
		calculations {D, S}
		2. Details that are not directly
	What was proved and what "skipped" {T, D}	relevant to the work of the
	4. Beauty, aesthetics {T}	students {S}
	5. Intermediate summaries {S}	3. Stages that are too difficult to
	6. Proof structure, proof type (e.g., proof by induction)	the current level of the students


Ying-Lin Zhao

Jianlei Yang
email: jianlei@buaa.edu.cn

Weisheng Zhao
email: weisheng.zhao@buaa.edu.cn

IEEE Senior Member Aida Todri-Sanial

Yuanqing Cheng
email: yuanqing@ieee.org

Ieee Student Member

CCF/IEEE/ Acm Member

Power Supply Noise Aware Task Scheduling on Homogeneous 3D MPSoCs Considering the Thermal Constraint

Keywords: power supply noise (PSN), power delivery network (PDN), task scheduling algorithm, temperature, 3D MPSoCs Bulk caps MB decaps Pkg. decaps RDL Pkg. substrate

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

With the exponential increase of transistor count on-chip and insatiable demand of high performance, the power density on-chip increases dramatically. "Power Wall" issue becomes a serious concern for modern VLSI designers [START_REF] Borkar | The future of microprocessors[END_REF]. The stringent power constraint makes it extremely difficult to squeeze extra performance by simply scaling the clock frequency. As a result, MPSoCs (Multi-Processor System on Chips) emerge as an effective technique to continue Moore's law, especially in the embedded system domain [START_REF] Martin | Overview of the MPSoC design challenge[END_REF] because of their better energy efficiency. Moreover, MPSoC design methodology facilitates integration of various IP cores from different vendors, which reduces the design complexity and accelerates time-to-market greatly.

Recently, the emerging 3D integration technology is adopted in the MPSoC design (i.e., 3D MPSoCs) to approach higher integration density and more functionalities than the 2D counterpart [START_REF] Todri-Sanial | Physical Design for 3D Integrated Circuits[END_REF]. By stacking several thinned tiers vertically, data communication bandwidth and power consumption can be improved greatly with the aid of through-siliconvias (TSVs). However, the 3D MPSoC architecture also presents several challenges due to the die-stacking structure. Among them, signal integrity is a critical issue for chip reliability. Since IP cores residing on different tiers commonly share a power delivery network [START_REF] Tendler | POWER4 system microarchitecture[END_REF], the activities on one core may propagate to cores in its vicinity by the shared power delivery network. The shrinking power supply voltage and increasing magnitudes of current transients make the power supply noise (PSN) more significant on 3D MPSoCs compared with their 2D counterparts. To constrain the PSN magnitude, many effective methods are proposed from different optimization perspectives. Todri et al. investigated the PSN interactions on a multi-processor platform, and derived several guidelines for workload assignments to suppress the PSN [START_REF] Todri | Power supply noise aware workload assignment for multi-core systems[END_REF]. Wang et al. optimized the task mapping and scheduling to minimize the PSN induced by power gating [START_REF] Wang | Power Gating Aware Task Scheduling in MPSoC[END_REF]. Although their work provides insights of the PSN effect in traditional MPSoCs, the proposed method can not be simply extended to 3D MPSoCs due to the following reasons. First, each tier manifests different characteristic impedance and may experience different voltage drop [START_REF] Huang | Power delivery for 3D chip stacks: Physical modeling and design implication[END_REF]. Second, the PSN can propagate from one tier to other tiers through TSVs, which introduces non-negligible PSN couplings. As a result, the heterogeneity of die-stacking structure and complicated PSN interactions require a novel hardware-software co-design methodology for 3D MPSoCs to suppress PSN effectively.

On the other hand, the reliability of 3D MPSoCs is also threatened by the thermal issue [START_REF] Sabry | Towards thermally-aware design of 3D MPSoCs with inter-tier cooling[END_REF]. Stacking several tiers together presents a severe challenge on thermal dissipation. High temperature can aggravate the NBTI (Negative Bias Temperature Instability) and the hot carrier injection effect [START_REF] Kufluoglu | A unified modeling of NBTI and hot carrier injection for MOSFET reliability[END_REF]. Since upper tiers are thinned before integration to facilitate die stacking, the vertical thermal correlation dominates the heat dissipation in 3D MPSoCs, which makes the thermal modeling of 3D MP-SoCs different from those of 2D counterparts.

In the paper, we explore to deal with the above two reliability concerns from the task assignment perspective for hard real-time applications on homogeneous 3D MPSoCs. In the hard read-time application, the task graph extracted is predetermined and the deadline must be guaranteed [START_REF] Micheli | Synthesis and Optimization of Digital Circuits[END_REF]. With an illustrative example, we show that different task mapping and scheduling schemes may result in significantly different PSN distributions, which implies the large optimization potential by PSN aware task scheduling. However, we observe that the conventional thermal aware task assignment scheme may cause severe PSN, which motivates our work. In order to optimize task scheduling with both thermal and PSN concerns, we propose a framework to evaluate the PSN and thermal distributions effectively. First, we extract representative power traces from real applications, and convert them to current stimuli traces instead of the traditional triangular or trapezoidal current stimuli to make the PSN calculation more accurate and realistic. Second, we construct a power delivery network (PDN) model of 3D MPSoCs for PSN calculations, and develop a fast power grid solver to facilitate PSN analyses. Based on these modeling techniques, we formulate the task scheduling optimization as an linear programming problem, which minimizes the PSN with the peak temperature constraint. Then, a list-scheduling based heuristic algorithm is proposed to obtain the optimal task scheduling solution. Extensive simulation results show that the proposed algorithm can reduce PSN by 12% on a 2 × 2 × 2 MPSoC and 14% on a 3 × 3 × 3 MPSoC platform compared with the state-of-the-art thermal aware task scheduling scheme [START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF]. Additionally, task execution time can be improved by 5.5% and 7.8% respectively due to the reduced PSN.

Our main contributions are listed as follows.

We proposed an efficient architecture- For the ease of understanding, some necessary background knowledge is introduced as follows. As suggested in [START_REF] Chen | Power Supply Noise Analysis Methodology For Deepsubmicron Vlsi Chip Design[END_REF], it is necessary to consider both package and on-chip power delivery network for accurate PSN prediction. Traditionally, the package is modeled considering its inductive effect while on-chip interconnects are modeled considering their resistive and capaci-tive effects. However, as the working frequency increases, on-chip inductance can no longer be ignored [START_REF] Zhuo | A silicon-validated methodology for power delivery modeling and simulation[END_REF]. In the paper, we model both the package and on-chip PDNs to capture PSN accurately.

We assume the on-chip PDN is in the mesh topology and shared by all cores on-chip as similar to [START_REF] Khan | Power Delivery Design for 3-D ICs Using Different Through-Silicon Via (TSV) Technologies[END_REF]. The power and grid lines interleave with each other in one metal layer and are orthogonally aligned on different layers for PSN reduction. P/G interconnects on different layers are connected by vias and deliver the power from global metal layers to local metal layers.

A simplified model of a typical mesh PDN for 3D homogeneous MPSoC is shown in Fig. 2.

As shown in the figure, current is delivered from the package to the on-chip PDN through P/G C4 bumps, and the power supplies of upper tiers are provided from the bottom tier through P/G TSVs similar to the structure mentioned in [START_REF] Healy | Power delivery system architecture for many-tier 3D systems[END_REF].

Then, the PSN can be calculated as follows [START_REF] Andrew | Noise considerations in circuit optimization[END_REF]:

V pnoise = te ts max{V dd -V p , 0}dt/(t e -t s ), V gnoise = te ts max{V ss , 0}dt/(t e -t s ), V noise = V pnoise + V gnoise .
where t s is the start of the timing window for the PSN calculation, and t e is the end of the timing window. V dd is the normal power supply voltage. V p is the real voltage of the power grid node under investigation, and V ss is the ground bounce of the corresponding ground grid node.

Using the above equations, we can calculate the PSN magnitude of each P/G grid node considering both voltage drop (V pnoise ) and ground bounce (V gnoise ).

Thermal Modeling Techniques for 3D MPSoCs

Since the thermal issue is another important concern for 3D ICs, it is imperative to consider the thermal constraint during workload assignment optimization for 3D MPSoCs.

In order to capture on-chip thermal distribution, an accurate thermal model is required.

Thermal modeling techniques for 3D ICs can be classified into several categories.

Solve the heat flow equation directly to get the temperature distribution on-chip by the finite element method or finite differential method [START_REF] Sun | Threedimensional multiprocessor system-onchip thermal optimization[END_REF][START_REF] Huang | Parameterized physical compact thermal modeling[END_REF].

Utilize duality between the thermal and the electrical properties. The thermal conductivity can be modeled as the resistance in the equivalent electrical circuit. The temperature difference corresponds to the voltage difference. The power consumption can be modeled as the current source. Then, the temperature of each node can be solved by circuit analyses [START_REF] Todri | A study of tapered 3-D TSVs for power and thermal integrity[END_REF].

Utilize on-chip power information such as the power gradient, to roughly estimate the temperature variations among functional blocks or cores [START_REF] Zhou | Thermal-Aware Task Scheduling for 3D Multicore Processors[END_REF].

The first method can obtain the accurate solution, but the computing complexity is too high to be adopted for the large scale of MP-SoCs. The last one is the fastest method but it can only be used for qualitative analyses lacking of enough accuracy. The second method listed above makes a good trade-off between the accuracy and the efficiency. The widespread used thermal simulation tool Hotspot [21] is based on the second method and we will use it to evaluate the thermal distribution in this paper.

Introduction to Task Graph

In the paper, we assume that the running application can be split into a number of tasks with specified timing dependencies and constraints. Then, the application can be represented by a directed acyclic task graph, which is widely used for task scheduling research [START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF].

A task graph example is shown in Fig. 3

Fig. 4: (a) The flow chart of the list scheduling scheme [START_REF] Micheli | Synthesis and Optimization of Digital Circuits[END_REF]. (b) The thermal aware scheduling algorithm [START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF].

Motivation

In this section, we investigate PSN distributions caused by different task allocation schemes. For the completeness of the paper, we briefly introduce the task allocation schemes used in our investigation. The first scheme is based on the conventional list scheduling algorithm [START_REF] Micheli | Synthesis and Optimization of Digital Circuits[END_REF] as shown Fig. 4 The second scheme is the state-of-the-art thermal aware task scheduling algorithm proposed by [START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF] as shown in Fig. 4(b). The scheduler evaluates the thermal distribution on-chip at each scheduling point for each possible task assignment, and the scheduler chooses the best candidate position approaching the lowest peak temperature. The third scheme is similar to the thermal aware scheduling but evaluates PSN instead. At each schedule point, the scheduler will assign the ready task to the available position approaching minimal PSN (the PSN evaluation procedure will be detailed in the next section).

To illustrate scheduling results using the three task assignment schemes, we use TGFF [START_REF] Dick | TGFF: task graphs for free[END_REF] As shown in Table 1, the random task assignment scheme can be neither thermal nor PSN friendly. Moreover, we can observe that the thermal aware scheduling scheme may generate severe peak PSN (increasing 18% compared with that of the PSN-aware case). In contrast, PSN aware task scheduling scheme may incur higher peak temperature than that of thermal aware scheduling algorithm.

To examine the conflict between the thermal aware scheduling scheme and the PSN aware scheduling scheme, we investigate the thermal and PSN distributions of each tier when running a single task on different tiers as shown in Fig. 5. In case 1, the task is assigned to the bottom tier. In case 2, it is assigned to the middle tier. In case 3, it is assigned to the top layer. In Fig. 5, we assume that the bottom tier is attached to the PCB board and provides power supply for upper tiers while the top tier is attached to the heatsink for thermal dissipation. Both the peak temperature and the PSN magnitude of each tier are shown in Table 2.

As shown in Table 2, the peak PSN magnitude is the largest when the task is assigned to the top tier (63.4mV). The peak PSN magnitude is the smallest when the task is assigned to the bottom tier (54.8mV). From the power supply noise suppression perspective, it is prefer-able to schedule the task near the bottom tier as much as possible. Since the power supply has to go through the bottom and the middle tier to reach PDN on the top tier, the top tier suffers from more severe PSN than other tiers [START_REF] Xu | Modeling of power delivery into 3D chips on silicon interposer[END_REF]. On the other hand, when the task is allocated on the bottom tier, the peak temperature is the highest (304.8K) among all three cases. Therefore, from the heat dissipation perspective, it is better to assign the task in upper tiers which are closer to the heat sink. As a result, there is conflict between the PSNaware task scheduling and the thermal-aware task scheduling, which is coincide with [START_REF] Todri | A study of tapered 3-D TSVs for power and thermal integrity[END_REF].

The above analyses imply that it is necessary to consider both thermal and PSN issues during the task scheduling to ensure the reliability and availability of 3D MPSoCs. We choose Wattch [START_REF] Brooks | Wattch: A Framework for Architectural-Level Power Analysis and Optimizations[END_REF] for power trace extraction since it can get a satisfied trade-off between the running speed and the accuracy for a single core simulation. Note that our proposed framework does not depend on the specific simulator.

Then, the generated power trace can be converted to current traces and integrated with the PDN model. Here, we will take a SPEC2000 application "ammp" as an example to illustrate the workload characterization process as shown in Fig. 7.

Considering the large scale of power grid, it cannot afford to apply the entire power trace for PSN calculations, which will incur unacceptable running time overhead. Therefore, it is necessary to capture the representative segment of the extracted power trace. We use Sim-Point [START_REF] Sherwood | Automatically characterizing large scale program behavior[END_REF] to identify several different running phases of "ammp". For each identified running phase, we fast forward 1 million instructions for the cache warm-up and perform detailed timing simulation for another 1 million instructions (refer to Section 5 for our architecture simulation setup). Then, we extract 10000 cycle long segment from the generated power trace, which can capture the peak power consumption. Although the power consumption has close relationship with power supply noise, we observe that the maximum PSN may not exactly happen at the same time when the peak power appears due to the propagation delay of PDN.

To capture the worst PSN exactly, we take the generated power trace segment as input and use

Voltspot [START_REF] Zhang | Architecture implications of pads as a scarce resource[END_REF] to identify the interval including C4 bumps distribute on the bottom layer to connect the on-chip PDN to the off-chip PDN.

Fig. 8 illustrates the on-chip PDN model [START_REF] Cheng | Power supply noise-aware workload assignments for homogeneous 3D MPSoCs with thermal consideration[END_REF] while the off-chip model is derived from [START_REF] Gupta | Understanding voltage variations in chip multiprocessors using a distributed power-delivery network[END_REF]. In contemporary VLSI design, the power grid mesh can easily contain millions of nodes for the PSN calculation. It imposes a great challenge on power grid analysis. As the traditional simulation using HSPICE can no longer be applied for such a very large scale problem, many efficient numerical solving methods have been proposed considering the regularity of the power grid structure, such as multi-grid method [START_REF] Nassif | Fast Power Grid Simulation[END_REF][START_REF] Su | Full chip leakage estimation considering power supply and temperature variations[END_REF], preconditioned conjugated gradient method [START_REF] Chen | Efficient large-scale power grid analysis based on preconditioned krylov-subspace iterative methods[END_REF].

In order to reduce the simulation complexity, we construct a power grid hierarchy, i.e., the power grid in one core consists of several base grids while each base grid is composed of several base cells as in [START_REF] Todri | Power supply noise aware workload assignment for multi-core systems[END_REF]. Although the PDN model is largely simplified by the hierarchical structure, it would be still very time-consuming for PSN computations in task allocation and scheduling as the scheduling algorithm usually involves many trial-and-fail iterations to obtain the final solution. Therefore, we develop an efficient PDN solver to accelerate PSN analysis based on the modified nodal analysis (MNA).

To verify the effectiveness of the PDN solver, we generate the netlist of a 2 × 2 × 2 3D MPSoC and feed it into the PDN solver to calculate its pulse response. The simulation results on some selected power grid nodes are shown in Fig. 9. The simulation error of the PDN solver is negligible compared with the HSPICE simulation.

Problem Formulation

As stated in Section 3, to ensure reliable operations of 3D MPSoCs, we need to consider both thermal and PSN issues during the task scheduling. To clearly formulate the problem, we firstly give 3D MPSoC architecture and task graph definitions as follows, 3D MPSoC Architecture The 3D MPSoC architecture can be described as AR(m, n, l), where l is the layer count, and each layer has m × n cores. All processing elements (PEs for short) within a layer are interconnected by a 2D mesh Network-on-chip (NoC) structure. PEs on different layers are connected through TSVs, as proposed in [START_REF] Li | Design and Management of 3D Chip Multiprocessors Using Network-in-Memory[END_REF].

All PEs within the 3D MPSoC share a global power grid, and the power supply is delivered from the bottom layer to upper layers through power supply TSVs, as shown in Fig. 2.

Task Graph Definition

The application running on the MPSoC can be split by a set of tasks executing concurrently or in a specified order. As shown in Fig. 3, S is the vertex set of task graph G(S, E). S i denotes task i. Its weight t i denotes the execution time. If task i is

In the paper, we use tier and layer interchangeably.

a predecessor of task j, then they should satisfy the following constraints, t s (j) ≥ t e (i), where t s (j) is task j's start time and t e (i) is task i's finish time. Additionally, all tasks should meet the deadline constraints, i.e., t e (i) ≤ d(i) where d(i) is the deadline of task i.

Then, the task scheduling problem can be formulated as follows, min.

S i ∈S,p∈P

x ip P SN (p, S i ). s. t. ∀S i p x ip = 1, (1)
t e (S i ) = t s (S i ) + t i ), (2)
t s (S i ) ≥ max e ji ∈E {t e (S j )},

t e (S i ) ≤ d S i , (3)
t s (S i ) ≥ t e (S j ), (4)
p ij + p ji = 1, (5)
max p∈P T p (t) ≤ T 0 , (6)
t ≤ SL,

GV(x) + C dV(x) dt = MAI, (8)
x ∈ power grid nodes,

P SN (p, S i ) = max|V (x k , S i ) -V dd |, (9)
x k ∈ core p.

where,

x ip =             
1 if task S i is allocated to core p 0 otherwise

p ij =                                  1 if task S i is scheduled before S j
and both of them are allocated to the same core 0 otherwise

As shown above, our optimization target is to minimize the PSN magnitudes of running cores by task scheduling. (1) means that every task S i can only be allocated to a single core.

S is the task set and P is the core set. [START_REF] Martin | Overview of the MPSoC design challenge[END_REF] derives the finish time of task S i , where t i denotes the task i's execution time. ( 3) is used to guarantee the task precedence during the task scheduling, i.e., a task can only be scheduled after all its predecessors finish execution. [START_REF] Tendler | POWER4 system microarchitecture[END_REF] guarantees that the deadline constraint can not be violated. ( 5) and ( 6) maintain the execution order when two tasks are allocated on the same core. [START_REF] Huang | Power delivery for 3D chip stacks: Physical modeling and design implication[END_REF] makes sure that the peak temperature of the 3D MPSoC must be lower than the temperature constraint T 0 . SL is the task schedule time length. At each schedule point, power supply noise can be calculated by ( 8) and ( 9).

In the next subsection, we will propose a Algorithm 1 PSN and thermal aware task scheduling algorithm update core status(spec.core, scheduling point); cur time ← scheduling point is O(Cp 0 q 0 ). p 0 is the time of one thermal simulation for a single core, and q 0 is the time of one PSN calculation for a single core. In the worst case, we need totally S × C thermal simulations and PSN calculations to obtain the optimal schedule. As a result, the time complexity of the algorithm is O(SC 2 p 0 q 0 ) or O(SC 2 ) since p 0 and q 0 are constants.

Note that we assume that the task graph to be run on the 3D MPSoC is determined in advance similar to [START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF][START_REF] Zhou | Thermal-Aware Task Scheduling for 3D Multicore Processors[END_REF]. Therefore, our proposed algorithm can run off-line to derive the optimal task scheduling. Although the iterative optimization procedure involves power supply noise and temperature evaluations, the running time overhead is acceptable due to the linear increase of the time complexity with the number of tasks. Moreover, since the algorithm is off-line, it does not need to make the task assignment decision during the run time, and can guarantee quick scheduling response during the run time.

Experimental Results

In this section, we describe the experimental setup firstly and then present the experimental results of the proposed task scheduling algorithm. In addition to E3S benchmarks, we also use TGFF [START_REF] Dick | TGFF: task graphs for free[END_REF] to generate eight different hypothetical task graphs suitable for evaluations on the large-scale 3D MPSoC. The specifications of E3S and synthesized benchmarks are shown in Table 3. The first column is the name of the benchmark. The second and the third column denote the task number and the edge count between tasks respectively. Since task power traces used for PSN evaluations are not available from task graph specifications, we take power trace extracted from SPEC2000 benchmarks instead, and different SPEC2000 benchmarks correspond to different tasks. In practice, task power traces could be obtained with the technique described in Section 4. according to measurements from a prototype of many-core processor [START_REF] Howard | A 48-Core IA-32 messagepassing processor with DVFS in 45nm CMOS[END_REF]. Another one has 3 tiers and each tier has 3×3 homogeneous cores.

To verify the effectiveness of our proposed algorithm, we implement a thermal-aware task scheduling algorithm proposed by [START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF] for comparisons. Our proposed task scheduling algorithm can reduce PSN by 12% on average compared with the task scheduling scheme proposed in [START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF].

PSN Reductions of Our

Then, we schedule tasks on the 3 × 3 × 3 The thermal constraint is still set to 320K. As shown in Fig. 11, increasing core power induces more severe PSN. Compared with [START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF], our proposed method can reduce PSN by 10.2% for the 2 × 2 × 2 MPSoC case and by 14.8% for the 3 × 3 × 3 MPSoC case.

P o w e r s u p p l y n o i s e ( V ) T h e m e t h o d p r o p o s e d i n [ 1 0 ] O u r p r o p o s e d m e t h o

Running Performance & Temperature Comparisons

PSN may not only be detrimental to the system reliability but also increase critical path delay variations, which may severely degrade the task running performance. For example, Saint-Laurent and Swaminathan analyzed the relationship between the power supply noise and the clock frequency, and claimed that 63mV PSN variation can slow down clock frequency by 6.7% at 130nm technology node [START_REF] Saint-Laurent | Impact of power-supply noise on timing in high-frequency microprocessors[END_REF]. Therefore, the PSN-aware task scheduling algorithm is beneficial for the task running performance as well. We use the formula proposed by [START_REF] Saint-Laurent | Impact of power-supply noise on timing in high-frequency microprocessors[END_REF] to model the relationship between the average PSN and the critical path delay, i.e., The critical path delay variations may degrade the processor running frequency and the task execution time. For example, when the critical path delay increases by 20% due to the PSN, the clock frequency would have to be decreased accordingly to prevent logic errors. Therefore, the task execution time will increase. In the experiment, according to the PSN distributions during the task scheduling procedure, the clock frequency when running different tasks can be obtained by Eq. [START_REF] Micheli | Synthesis and Optimization of Digital Circuits[END_REF].

D D 0 = 1 -k 1 ∆V V dd -V t + k 2 ( ∆V V dd -V t ) 2 . ( 10
Then, the updated clock frequency is used to derive the task execution time. Fig. 12 illustrates the final completion time when running different task graphs with the thermal-constrained algorithm proposed in [START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF] and our proposed algorithm assuming the core power is The peak temperature comparisons caused adjusted the core activities at different layers according to their distances from the heatsink such that the hotspot will not occur [START_REF] Hameed | Dynamic thermal management in 3D multicore architecture through run-time adaptation[END_REF]. This method is combined with DVFS to improve the chip performance by run-time adaption with the thermal consideration.

For MPSoCs, task mapping and/or scheduling is another important research topic.

Some work focuses on improving the performance under some constraints such as [START_REF] Coskun | Temperature Aware Task Scheduling in MPSoCs[END_REF][START_REF] Jayaseelan | Temperature aware task sequencing and voltage scaling[END_REF][START_REF] Liao | An online thermal-constrained task scheduler for 3D multi-core processors[END_REF] (thermal constraint), [START_REF] Momtazpour | Power-yield optimization in MPSoC task scheduling under process variation[END_REF] (power aware task scheduling). On the other hand, increasing power density inspires the research for energy minimization, such as [START_REF] Hu | Energy-and performance-aware mapping for regular NoC architectures[END_REF]58]. Since task map-ping/scheduling gets rid of changing the low level hardware design, it can improve the system adaptability for different types of applications with relative low overheads, and will become more important with the prevalence of 3D MPSoCs.

Conclusions

As transistor integration density increases continuously, more cores can be fabricated on a single chip to implement more functionalities and approach higher energy efficiency. Moreover, with the emergence of 3D integration technology, many core MPSoCs can be packaged in smaller footprints and achieve higher performance. Although 3D MPSoCs bring huge opportunities for high performance system design, they also have some challenging problems. Among them, power supply noise interactions among different cores and tiers be-

  level PSN simulation framework to fill the gap between circuit-level PSN simulation and architecture-level task scheduling for 3D MPSoCs. Our another contribution is considering both power supply noise and temperature to effectively avoid hotspot during the PSN optimization for 3D MPSoCs. We propose a novel list-scheduling based heuristic algorithm for the task scheduling problem on homogeneous 3D MP-SoCs with both thermal and PSN considerations. Extensive simulation results show that the proposed algorithm can reduce PSN by 12% on a 2 × 2 × 2 MPSoC and 14% on a 3 × 3 × 3 MPSoC compared with the state-of-the-art thermal aware task scheduling scheme [11]. Additionally, task execution time can be improved by 5.5% and 7.8% respectively due to the reduced PSN The rest of the paper is organized as follows. Section 2 presents the preliminaries of 3D MPSoC PDN and thermal modeling techniques. Task graph is also introduced in this section. An illustrative example is presented in Section 3 to motivate our work. Section 4 formulates the PSN aware task scheduling problem with the thermal constraint and proposes a framework to solve it. The computing complexity analysis of the proposed algorithm is given in this section as well. Section 5 shows the experimental results by running our task scheduling algorithm extensively on different scales of 3D MPSoCs. Section 6 presents the related work and Section 7 concludes the paper. 2 Preliminaries on Power Delivery Network and Thermal Modeling Techniques of 3D MPSoCs

Fig. 1 :

 1 Fig. 1: The power delivery system including both off-chip and on-chip components.

Fig. 2 :

 2 Fig. 2: On chip mesh grid power delivery network of homogeneous 3D MPSoCs.

a, b

 b Both PSN and temperature values are the peak values among all cores on the same tier.

Fig. 5 :

 5 Fig. 5: Running a single task on different tiers for thermal and PSN comparisons: (1) running the task on the bottom tier; (2) running the task on the middle tier; (3) running the task on the top tier.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Proposed task scheduling framework considering both thermal and PSN issues.

4 . 2

 42 the worst PSN. Then, we back-annotate the interval to the original power trace segment for the PDN stimuli extraction. Consequently, the In the paper, we use workload and task interchangeably Since the Voltspot-based PSN simulation is only performed on a single task in this paper, the run time overhead of Voltspot is acceptable.extracted stimuli are inserted at current source insertion points of the PDN model for PSN calculations, which will be detailed in the next subsection. Development of the PDN Model and the PDN Solver Since we focus on the PSN at the corelevel and emphasize the power supply interactions between different cores, it is enough to only consider the global power grid, which takes each core as one block as in [5]. Considering the on-chip PDN, each interconnect segment is modeled with its distributed RLC parasitics.Decoupling capacitance, including intrinsic and external decoupling capacitance, is assumed to be distributed evenly across the core, and connected in parallel with the current source derived from the power trace generated above to the switching activity of the task running on it.Note that both power and ground grids are considered for PSN calculations. Power/ground grids on each layer are interconnected by TSVs, which are modeled as resistors and inductors.

Fig. 8 :

 8 Fig. 8:

Fig. 9 :

 9 Fig. 9: Simulation result comparisons between our PDN solver and HSPICE simulations on four sample power grid nodes. (a) Simulation results of the PDN solver. (b) HSPICE simulation results.

30 : 4 . 4

 3044 return P SN schedule solution heuristic algorithm to solve the problem effectively. Our Proposed Task Scheduling Algorithm As shown in Algorithm 1, the inputs to the algorithm include the 3D MPSoC specification, current stimuli derived from the power trace extraction, and the task graph. The output is the optimal task schedule. The algorithm is constructed based on the widely-used list scheduling algorithm[START_REF] Kwok | Static Task Scheduling And Allocation Algorithms For Scalable Parallel And Distributed Systems: Classification And Performance Comparison[END_REF]. First of all, the earliest start time of each task is calculated by ASAP (i.e., as soon as possible) algorithm. The latest start time is calculated by ALAP (i.e., as late as possible) algorithm. Then, all tasks are sorted by their mobilities (i.e., the difference of the latest start time and the earliest start time of the task) in the ascending order such that the task with the least mobility can be scheduled firstly to avoid the violation of the deadline requirement.At the beginning of the schedule, the first task is put into the ready list. During the schedule, all tasks whose parents finish executions are put into the ready list for scheduling. At each schedule point, ready tasks are assigned to idle cores in an iterative manner.For each assignment trial, the PSNs of all running cores are calculated by the PDN solver mentioned above. At the same time, the peak temperature of each trial is evaluated using Hotspot[21]. As a result, the core incurring the minimum PSN value while meeting the peak temperature constraint is chosen for the task assignment. Since the thermal constant is in the range of milliseconds[START_REF] Choi | Thermal-aware task scheduling at the system software level[END_REF], we use the average power consumption of each task instead of the transient power for the thermal simulation to accelerate the simulation speed. Additionally, as mentioned in[START_REF] Huang | Lifetime reliability-aware task allocation and scheduling for MPSoC platforms[END_REF], significant thermal/PSN fluctuation occurs when there is a new task beginning to run or an old one finishing execution. Therefore, we define the schedule point as the time point when there is any task ending execution or beginning to run, and we only perform the PSN and thermal evaluations at each scheduling point, which reduces the computing overhead further. When the ready list becomes empty, it means all tasks have been scheduled and the optimal schedule can be obtained. The timing complexity of the proposed algorithm is analyzed as follows. Assume the task graph has S tasks and the 3D MPSoC has C = l × m × n cores, where l is the number of tiers, and each tier has m × n cores. The worst case is that every task has only one parent and only one child. In this case, at each schedule point, the core candidate for assign-ment is C. For each candidate, we need to perform one thermal simulation and one PSN calculation, whose running time mainly depends on the thermal and power grid sizes. Assume that the base grid size is a constant. Then, the number of thermal and PDN grids depends on the number of tiers and the number of cores on each tier. Therefore, the time complexity of the thermal simulation or the PSN calculation

  connect parasitics are derived based on 45nm PTM interconnect model. TSV parasitics are obtained from[START_REF] Cadix | Integration and frequency dependent electrical modeling of Through Silicon Vias (TSV) for high density 3DICs[END_REF]. To evaluate the temperature using Hotspot, it requires to obtain the power trace of the running task. As mentioned in Subsection 4.1, we firstly use the architecture level simulation to get the power trace when a specific task runs on a core. Because the thermal constant lies within the range of several milliseconds which is much larger than the clock cycle time (within nanosecond range), we pick the average power for the thermal simulation. The leakage power of idle cores is also taken into account during the thermal simulation. With these power information and the Hotspot configuration listed in Table6, we can get the temperature distributions on-chip in each scheduling step.Two kinds of MPSoCs are used in our evaluation. The first one has two tiers and each tier has 2 × 2 homogeneous cores. The power consumption of the core is assumed to be 4.6W

First, the 2 × 2 ×

 22 2 homogeneous MPSoC is considered. During the PSN calculations, the worst case voltage drop during the whole task scheduling procedure among all power grid nodes is chosen for comparison. The temperature constraint is set to 320K. The comparison results are shown in Fig. 10(a). As shown in Fig. 10(a), different benchmarks have significantly different PSN distributions due to their various switching activities.

  MPSoC and the comparison results are shown in Fig. 10(b). The power supply noise magnitudes on the 3 × 3 × 3 MPSoC are generally smaller than those of the 2 × 2 × 2 MPSoC case. It is because more cores are idle during the scheduling procedure and can provide more capacitance to suppress the transient PSN. Our proposed algorithm can reduce as much as 17%power supply noise compared with the work in[START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF] with the same thermal constraint. It indicates the good scalability of our algorithm.In the above experiments, we observe that

Fig. 10 :

 10 Fig. 10: PSN comparisons of our proposed task scheduling algorithm and the thermal aware task scheduling algorithm [11] given the same thermal constraint. (a) Running tasks on the 2 × 2 × 2 MPSoC. (b) Running tasks on the 3 × 3 × 3 MPSoC.

Fig. 11 :

 11 Fig. 11: PSN comparisons of our proposed task scheduling algorithm and the thermal aware task scheduling algorithm given the same thermal constraint when the core power is doubled. (a) Running tasks on the 2 × 2 × 2 MPSoC. (b) Running tasks on the 3 × 3 × 3 MPSoC.

  9.2W.As shown in Fig.12, due to the reduced PSN, the task completion time also improves by the proposed task scheduling algorithm. For the 2 × 2 × 2 MPSoC case, the task completion time can be improved by 3.2% on average and 5.5% in maximum. For the 3 × 3 × 3 MPSoC case, the task completion time can be improved by 4.4% on average and 7.8% in maximum. The task completion time of task graphs with 4.6W core power also shows the similar trend and is not plotted due to the lack of space. The above experimental results validate the effectiveness of our proposed algorithm in terms of the PSN reduction and the running task performance improvement.

[ 40 ]a u t o -i n d u s t c o n s u m e r n e t w o r k i n g o f f i c e -a u t o m a t i o n t e l e c o m t g f f 1 t g f f 2 t g f f 3 t g f f 4 t g f f 5 t g f f 6 t g f f 7 t g f f 8 a u t o -i n d u s t c o n s u m e r n e t w o r k i n g o f f i c e -a u t o m a t i o n t e l e c o m t g f f 1 t g f f 2 t g f f 3 t g f f 4 t g f f 5 t g f f 6 t g f f 7 Fig. 12 :

 408712 Fig.12: Task graph completion time improvements of the proposed task scheduling algorithm compared with that of the algorithm proposed in[START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF] under the same thermal constraint (assume the core power is 9.2W).

  come an imminent issue for consideration during the software-hardware co-design. In the paper, we investigated the PSN optimization of 3D MPSoCs from the task scheduling perspective. To capture PSN accurately and efficiently, we proposed a framework including PDN stimuli extraction based on the architecture level simulation, an efficient PDN solver for PSN calculations and a heuristic algorithm for task scheduling taking both PSN and ther-mal issues into account. Compared with the state-of-the-art task scheduling algorithm for 3D MPSoCs, our proposed algorithm could reduce PSN by 12% on the 2 × 2 × 2 3D MP-SoC and by 14% on the 3 × 3 × 3 3D MPSoC. The execution time can also be improved by 5.5% and 7.8% respectively due to the reduced PSN magnitudes. Moreover, the experimental results also showed the good scalability of our proposed algorithm as power consumptions of 3D MPSoCs increase. Simulation Contest in 2012. He was a recipient of IEEE ICCD Best Paper Award in 2013, and ACM GLSVLSI Best Paper Nomination in 2015. Weisheng Zhao received the Ph.D. degree in physics from the University of Paris-Sud, France, in 2007. From 2004 to 2008, he investigated Spintronic devices based logic circuits and designed a prototype for hybrid Spintronic/CMOS (90 nm) chip in cooperation with STMicroelectronics. Since 2009, he joined the CNRS as a tenured research scientist and his interest includes the hybrid integration of nano-devices with CMOS circuit and new nonvolatile memory (40 nm technology node and below) like MRAM circuit and architecture design. He has authored or co-authored more than 150 scientific papers (e.g Advanced Material, Nature Communications, IEEE Transactions etc.); he is also the principal inventor of 4 international patents. From 2014, he becomes a youth 1000 plan distinguished profes-sor in Beihang University, Beijing, China, and the associated editor for IEEE Transactions on Nanotechnology. Aida Todri-Sanial received the B.S. degree in electrical engineering from Bradley University, IL in 2001, the M.S. degree in electrical engineering from Long Beach State University, CA, in 2003 and Ph.D. degree in electrical and computer engineering from the University of California, Santa Barbara, in 2009. She is currently a research scientist for French National Center of Scientific Research (CNRS) attached to Laboratoire d'Informatique de Robotique et de Micro-lectronique de Montpellier (LIRMM). Previously she was an RD Engineer for Fermi National Accelerator Laboratory, IL where she was the recipient of John Bardeen Fellow in Engineering in 2009. She has also held visiting positions at Mentor Graphics, Cadence Design Systems, STMicroelectronics and IBM TJ Watson Research Center.

Calculate task mobility, and sort tasks with mobility Map ready task(s) on idle core(s) randomly Construct ready task list Is there any unscheduled task? Derive the next scheduling point, and update current time Y End N Inputs: task graph, MPSoC spec. Try to assign the task to all possible locations Evaluate the thermal distribution for each trial Find the best position with minimal peak temp. Thermal aware scheduling[10] List scheduling[21]

							. In
	the figure, a node in the task graph denotes a
	task of the running application, and an edge de-
	notes the task running priority and the running
	dependency. For example, task S 2 can only ex-
	ecute after S 1 finishes. The weight of the node
	(i.e., t i ) denotes the execution time of the task.
	For real-time applications, each task node has
	the deadline constraint and the task execution
	can not violate it.
		t 1	S 1	d 1
	t 2	S 2	d 2	t 3	S 3	d 3
	t 4	S 4		t 5	S 5	t 6	S 6
		d 4			d 5		d 6
		t i : task execution time
		d i : task deadline
	Fig. 3: An illustrative task graph example.

Table 1 :

 1 PSN and Temperature Comparisons of Three Task Assignment Schemes a

		Random T-aware PSN-aware
	PSN (mV)	147.6	174.7	143.2
	Temp. (K)	310.3	307.5	309.3

to generate a task graph and schedule it on a 2 × 2 × 2 3D MPSoC using these schemes. The task graph has 20 nodes and 30 edges. The task characterizations, detailed simulation setup, PDN and thermal model parameters are presented in Section 4 and Sec-tion 5 respectively. Table 1 indicates the comparisons among three algorithms (conventional list scheduling algorithm, i.e., the "Random" algorithm in the table, thermal aware scheduling algorithm and PSN-aware scheduling algorithm wihtout thermal consideration) in terms of temperature and PSN. a T-aware denotes the thermal aware task scheduling scheme and PSN-aware denotes the PSN aware task scheduling scheme. Both PSN and temperature values are the peak values among all cores.

Table 2 :

 2 Psn and Temperature Comparisons of Three Task Running Scenarios Temperature(K) b 304.8 303.5 302.77 303.67 303.51 302.78 303.26 303.1 302.79

			Case 1			Case 2			Case 3
		Bottom Middle	Top	Bottom Middle	Top	Bottom Middle	Top
	PSN(mV) a	54.8	46.6	46.5	42.4	59.8	49.3	41.1	48.2	63.4

  procedure pt schedule(G, spec, P DN param, thermal param, P SN prof iles table)

	2:	// G: task graph, spec: 3D MPSoC specification, P DN param: PDN parameters
	3:	// thermal param: thermal parameters, P SN prof iles table: PSN profiles of each task
	4:	construct ready list(&ready list, G, &task map); cur time ← 0
	5:	while ready list! = NULL do
	6:	ready list sort(&ready list, G); task ← task select(ready list, cur time)
	7:	for i ← 0, spec.core count do
	15:	if peak temp > max temp then
	16:	restore(task.id, i, &task map); continue
	17:	else
	18:
	21:	f ind solution ← true
	22:	update solution(&P SN schedule solution, task.id, i, cur time)
	23:	else
	24:	restore(task.id, i, &task map); continue
	25:	if f ind solution = f alse && slack = -1 then
	26:	return NULL
	27:	else
	28:

1: 8: if spec.core[i] = f ree then 9: update task map(task.id, i, &task map) 10: if task.f inish time > deadline[task.id] then 11: restore(task.id, i, &task map); continue 12: else 13: thermal sim time ← f inish time(task map) 14: peak temp ← thermal sim(task.id, i, spec.power table, thermal param, sim time) P SN value ← P SN eval(task.id, i, P SN prof iles table, P DN param) 19: if P SN value < optimal value then 20: optimal value ← P SN value; spec.core[i] ← busy; update ready list(task.id, i, &G, &task map, &scheduling point) 29:

Table 3 :

 3 Task Graphs Used in the Experiments

	Benchmark	Task count Edge Count
	auto-indust	24	21
	consumer	13	14
	networking	15	11
	office-automation	5	5
	telecomm	34	28
	tgff1	23	35
	tgff2	16	21
	tgff3	18	25
	tgff4	21	28
	tgff5	17	24
	tgff6	26	30
	tgff7	22	33
	tgff8	18	27
	5.1 Experimental Setup
	Our proposed task scheduling algorithm is
	implemented by C++. E3S benchmark suite
	is adopted in our experiments. E3S bench-
	marks are extracted from EEMBC benchmark
	suite and widely used in the task scheduling

research

[START_REF] Chantem | Temperature-Aware Scheduling and Assignment for Hard Real-Time Applications on MPSoCs[END_REF][START_REF] Cheng | Thermalconstrained task allocation for interconnect energy reduction in 3-D homogeneous MPSoCs[END_REF]

. The E3S benchmarks can be classified into five application categories, i.e., automotive, consumer, networking, office automation and telecommunications.

Table 4 :

 4 Architecture Parameters of a Single

	Core of the 3D MPSoCs
	CPU	Alpha 21264 2GHz
	Predictor	Bimodal predictor,
	BTB with 2-bit counter
	IFQ Size/LSQ Size	4/8
	L1 D$/I$	32KB/32KB
		64B block size
	4-way/1-way associative
		LRU replacement
	Unified L2$	1MB, 64B block size
		4-way associative
		LRU replacement

Table 5 :

 5 PDN Model Parameters in Our Ex-

	periments
	Interconnect		TSV
	segment length	200µm	diameter	10µm
	segment resistance	48mΩ	aspect ratio 1 : 8
	segment capacitance 6.8pF	resistance	20mΩ
	segment inductance 196pH	inductance 25pH
	C4 Bump		Core
	resistance	9.52mΩ size(mm)	3.2 × 3.2
	inductance	12.65pH mesh grid	16 × 16

Table 6 :

 6 Thermal Model Parameters Used for

	Temperature Evaluations
	Bulk Si thickness of bottom die	150µm
	(next to heat sink)
	Bulk Si thickness of other dies	50µm
	Cu metal layer thickness	0.42µm
	Si thermal conductivity	100.0W/(mK)
	Heat sink thermal conductivity 400.0W/(mK)
	HotSpot grid resolution	64 × 64
	Ambient temperature	27
	Architecture parameters of the core used
	for the power trace extraction are listed in Ta-
	ble 4. The extracted power traces are converted
	to current stimuli corresponding to the running
	tasks and fed into the PDN solver for PSN cal-

culations. The PDN and TSV parameters used in our PDN model are listed in Table

5

. Core size used in our experiments is derived from a 45nm 48-core IA-32 processor

[START_REF] Howard | A 48-Core IA-32 messagepassing processor with DVFS in 45nm CMOS[END_REF]

. The inter-PTM interconnect model. http://ptm.asu.edu.

Table 7 :

 7 Peak Temperature Comparisons of the Thermal-Aware Task Scheduling Algorithm

	and Our Proposed Algorithm (Unit: K)
		2 × 2 × 2		3 × 3 × 3
		Thermal-aware [11] Our method Thermal-aware [11] Our method
	auto-indust	309.88	311.36	312.03	316.99
	consumer	308.33	310.79	311.2	315.82
	networking	309.34	311.58	312.19	316.96
	office-automation	306.59	308.71	309.87	314.04
	telecomm	313.79	315.08	317.15	320.44
	tgff1	313.43	313.87	313.44	318.17
	tgff2	310.3	313.87	311.59	315.78
	tgff3	311.39	312.68	312.15	316.6
	tgff4	309.76	311.75	312.36	317.33
	tgff5	312.88	314.31	313.6	318.54
	tgff6	311.73	312.39	312.9	317.9
	tgff7	311.93	312.13	312.11	316.37
	tgff8	310.3	310.56	311.59	315.63

Yinglin Zhao and Yuanqing Cheng have equal contributions in this work. This research is partially supported by the National Natural Science Foundation of China under Grant No. 61401008, and the State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, under Grant No. CARCH201602.

Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(4): 551-562.


Reinhard Hochmuth
email: hochmuth@idmp.uni-hannover.de

Marcel Schaub

Andreas Seifert

Regina Bruder

Rolf Biehler

The VEMINT-Test: Underlying Design Principles and Empirical Validation

Keywords: Bridging course, diagnosis, transition, calculus, Rasch-Analysis

), who combined cognitive activity and action control theoretical approaches in the development of a threedimensional competence structure model, and on Anthropological Theory of Didactics, to explain content-related differences between dimensions of the model. Validating Rasch-analyses show that, in accordance with the design ideas, a three-dimensional Rasch-model fits with empirical data.

Introduction

The average dropout rates of mathematics and engineering programs in universities in Germany are 47% and 36%, respectively (Bildungsberichterstattung, 2014). These rates are higher than the overall average drop-out rate which is 33% for all study programs at German universities. In addition to the lack of acquisition of key competences such as the ability and willingness for selfreflection and self-motivation [START_REF] Hilgert | Schwierigkeiten beim Übergang von Schule zu Hochschule im zeitlichen Vergleich-Ein Blick auf Defizite beim Erwerb von Schlüsselkompetenzen[END_REF], the literature (e.g., [START_REF] Cramer | Schulmathematik und Studierfähigkeit [School mathematics and academic achievement[END_REF] highlights that the lack of prior mathematical school knowledge is one of the major reasons for the high proportion of dropouts.

As a measure to reduce the number of dropouts, most universities and higher education institutes have offered mathematical remedial activities in the form of bridging courses to support students' learning of university mathematics in recent years. The idea is to reduce the gap between school and university mathematics while maintaining the standards of the programs. One of the major challenges is to design remedial bridging courses that are sensitive to individual needs. For example, while some of the students need more support in simplifications of algebraic expressions, other students may need support in elementary calculus. It is also important for the students to know what prior knowledge is needed to take the courses at the university. To support students in deciding which of the modules of the bridging course to take, it is desirable to have an appropriate diagnostic tool available. Such tool should also measure the impact of bridging courses. A substantial content analysis is essential in order to provide detailed feedback to individual learners and advice to lecturers in choosing topics and in deciding how intensely topics should be taught in transition courses [START_REF] Biehler | Relating different mathematical praxeologies as a challenge for designing mathematical content for bridging courses[END_REF][START_REF] Hochmuth | A general scheme for a heterogeneous manifold of transitions[END_REF]. For more than 15 years, the universities of Darmstadt, and recently also Hannover, Kassel, and Paderborn, have been offering bridging courses in the cooperative project Virtual Entrance Tutorial for STEM subjects (VEMINT, STEM in German is MINT) for students who wish to pursue mathematics-related programs [START_REF] Bausch | VEMINT-Interaktives Lernmaterial für mathematische Vor-und Brückenkurse [Interactive learning material for mathematics pre-and bridging-courses[END_REF][START_REF] Fischer | Mathematische Vorkurse im Blended-Learning-Format: Konstruktion, Implementation und wissenschaftliche Evaluation [Mathematics preparation courses in blendedlearning-format: construction, implementation and scientific evaluation[END_REF]. In recent years, the authors have also worked on developing a diagnostic test, the VEMINT-test, which is the focus of this paper.

The structure of the paper is as follows. After sketching the main goals of the VEMINT-test, we outline basic ideas of the competence structure model that underlies our test design and provide a briefpraxeological content analysis of tasks assigned to the dimensions of the model. Finally, we present results from a Rasch-Analysis empirically validating the three dimensions of the competence structure model.

The Development of the VEMINT-Test

The development of the VEMINT-test follows two partly opposing, goals: While working as a diagnostic test to understand better students' prior knowledge and gaps, it should also help to evaluate the impact of bridging courses. In addition, the pre-test needs to give information in a short time so students can decide what modules they need to take in the bridging course. In recent years, the diagnostic test has been refined several times based on both empirical and theoretical findings. Thereby, our main aim was to develop a standardized diagnostic instrument in two essentially equivalent versions (Form A and Form B), which can be used every year at the beginning and at the end of a bridging course. An expert rating determined the particular content of the test, which focused on analysis and elementary algebra and took into account the German minimum standard requirements (see, Cooperation Schule Hochschule, 2014). The items were adjusted according to quality criteria for tests and technical possibilities (e.g., the use of the Moodle STACK plug-in, Sangwin, 2007).

The final test in two forms (A and B) was designed for 60 minutes and comprised 22 tasks from secondary levels I and II in German schools. The examined topics are algebraic terms, equations, functions and calculus (differentiation and integration). The test was developed using a threedimensional competence structure model that will be described next. Afterwards we present results from a Rasch-Analysis, considering data that has been collected in the winter semester of 2017/2018. These results empirically reproduce the three-dimensional structure, thus validating our test-design in this respect.

A Competence Structure Model and its Dimensions

The competence structure model is based on the idea of "Basic Mathematical Knowledge" (BMK), which has been introduced by Feldt-Caesar (2017) as follows:

Basic mathematical knowledge and skills refer to the mathematical knowledge, skills and abilities which are to be retrievable to all pupils at the end of the two secondary levels in the form of mathematical terms, theorems and procedures in the long term and independently of the situation, i.e. in particular without the use of aids. (Our translation, p. 182) BMK serves "as a prerequisite for successful further learning, especially in a course of study" (our translation, p. 180), which requires that knowledge be sustainable and connected in the sense of "intelligent knowledge" [START_REF] Feldt-Caesar | Konzeptualisierung und Diagnose von mathematischem Grundwissen und Grundkönnen. Eine theoretische Betrachtung und exemplarische Konkretisierung am Ende der Sekundarstufe II [Concepts and diagnosis of basics in mathematics[END_REF][START_REF] Weinert | Lehren und Lernen für die Zukunft-Ansprüche an das Lernen in der Schule [Teaching and learning for future requirements to learning in school[END_REF] and, furthermore, transferable and connectable with new content [START_REF] Feldt-Caesar | Konzeptualisierung und Diagnose von mathematischem Grundwissen und Grundkönnen. Eine theoretische Betrachtung und exemplarische Konkretisierung am Ende der Sekundarstufe II [Concepts and diagnosis of basics in mathematics[END_REF][START_REF] Nitsch | Schülerhandlungen als Elemente fachdidaktisch motivierter Kompetenzmodellierungen [Student's performance as elements of didactically motivated comptence modelling[END_REF]. For related diagnostic and feedback goals these ideas imply that items of a test should cover not only calculusoriented tasks but should also aim at "intelligent knowledge" and "understanding oriented knowledge" where the latter is not the same as "understanding." We agree with [START_REF] Skemp | Relational understanding and instrumental understanding[END_REF] that no "understanding," neither instrumental nor relational understanding, is validly testable without additional intersubjective interactions. On the other hand, "understanding oriented knowledge" including knowledge necessary for "relational understanding" beyond knowledge necessary for "instrumental knowledge" is an important basis for further learning [START_REF] Bruder | Mathematisches Grundwissen und Grundkönnen in der Sekundarstufe II[END_REF][START_REF] Skemp | Relational understanding and instrumental understanding[END_REF]. These general underlying goals call for a sample of tasks which cover various qualitative facets of knowledge and associated mental activities. Moreover the sample should be helpful both in regards to diagnostic and evaluation goals as well as for providing appropriate feedback. To cover and operationalize the idea of such different qualitative facets we have developed a three-dimensional competence structure model on the basis of ideas from Feldt-Caesar (2017) and applied Anthropological Theory of Didactics (ATD, [START_REF] Chevallard | Fundamental concepts in didactics: Perspectives provided by an anthropological approach[END_REF])) for the content analysis of tasks.

In Feldt-Caesar (2017), cognitive, activity and action control theoretical approaches are combined to describe and analyze mental activities with respect to five conceptual levels. Within our context, the levels "elementary actions," including identification and realization, and "basic actions," including recognizing, describing, linking, applying and justifying, are important. In Feldt-Caesar (2017), both types of actions have been related to the so-called "content elements" that are conceptualized in terms, theorems, and procedures. In view of our focus on analyzing test tasks within the institutional context of the transition from school to university mathematics, it turned out that a praxeological view on "content elements" was probably more appropriate for the current project.

Accordingly, in the following we apply a few basic praxeological notions from ATD: The simplified [P, L]-model with P representing the praxeological block (i.e., the technical aspect(s) connected to a type of task and) with L representing the technological-theoretical block. The latter covers in particular: describing a technique, validating (e.g., proving or justifying how and that a technique works), knowledge about the efficiency and motives of a technique as well as knowledge about variants and simplifications, and finally, knowledge required or useful for controlling the application of a technique, which is particularly relevant for connecting practices and praxeologies. Our starting point for the identification of P and L lies in the single tasks of the test, curricula school books and in the VEMINT group consented experiences concerning the actual implementation and institutionalization of praxeologies and corresponding technical and technological aspects of school mathematics. There are, of course, further relations between above mentioned cognitive notions like "instrumental" and "relational understanding": From the viewpoint of knowledge and meaning structures, they can be referred to qualitative differences in relationships between practical and technological-theoretical blocks of one or several praxeologies. A more detailed analysis of such issues, however, lies beyond the scope of this paper. Here, the praxeological notions mainly serve as a tool for describing and analyzing qualitative aspects of "content elements" with regard to the three dimensions of the competence structure model. Dimension I (which is associated to instrumental understanding) is characterized by elementary actions and cognitive operations such as identification and realization, and usually refer to a content element that does not have to be transferred to other content elements. The actions to be taken consist of a single step and are related to a "first elementary level" of mental activities in Feldt-Caesar (2017). Content-wise and in praxeological terms, Dimension I covers tasks from school that can be solved by techniques without especially taking into account technological aspects like supporting argumentations, proofs, or contextual embedding, etc. The techniques in Dimension I tasks are more or less extensively institutionalized in school mathematics, represent typical tasks of school examinations, and, at least partly, also appear in final exams (e.g., baccalaureates). A characteristic task in the test is the calculation of the derivative of It can be calculated by algebraic operations that can be executed without referring to basic rules and notions. This kind of tasks, focusing on techniques without links to technologies and supporting mathematical organizations, seems to be dominant in school internationally (e.g., [START_REF] Barbé | Didactic restrictions on the teacher's practice: The case of limits of functions in Spanish High Schools[END_REF].

In Dimension II, the one-step approach is maintained but a linking to content elements of the same topic is necessary to solve the associated tasks. Such tasks are characterized by the main reference to one content element and possibly to other content elements, directly related to the main content element. Besides elementary actions, cognitive operations such as describing, linking, applying, and justifying are necessary in most cases. These tasks cannot be solved by simple calculations and are often unfamiliar to students (so that they need probably relational understanding). Content-wise, Dimension II covers tasks that relate to technological-theoretical blocks of praxeologies implying validation and justification. Students are not sufficiently trained in techniques of Dimension II tasks such that such technological aspects are superfluous for solving the tasks. Moreover, in the school context, this type of tasks typically demands verbal descriptions or even verbal justifications. A further common aspect of Dimension II tasks is that the technological aspects need no additional validation, for example by linking to technological aspects of praxeologies living in other domains; hence they are of a local nature. Figure 1 presents an example for a Dimension II task. It is expected that to solve this task students use relationships between verbal, graphical, and symbolic representations and switch across those representations. In order to solve the task, the second derivative is to be interpreted as the curvature of the function f. What is unusual about this task is that the values of the second derivative are given and, conversely, a function f must be reconstructed based on the given information.

Dimension III tasks are multi-step tasks, and characterized by several elementary actions and cognitive operations (associated to "intelligent knowledge"). The tasks refer to content elements from at least two different content areas. Thus, solving of Dimension III tasks combines techniques from different praxeologies; the techniques involved are often more complex, or the technological aspects relevant for the combination of the techniques are either weakly established or combine aspects of different praxeologies. A task of this type, that combines techniques and is wellestablished in school, looks as follows (Feldt-Caesar, 2017): "The function is given by Determine the equation of the tangent , which touches the graph of the function at the point ." In this task, content elements of differential calculus must be linked and the results of the differential calculus must be used to establish a linear function (equation of a tangent). Thus, both content from secondary level I and secondary level II must be applied. Another task (item 13) of Dimension III is the following: "Simplify the following expression and collect the variables ." In this task, the required combination of techniques from division of fractions and power calculations is nested; in addition, related technological aspects have to be combined in an appropriate way. This means that it is not enough to apply simple and local techniques from different domains. Content-wise, the main characteristic of Dimension III tasks is the link of different techniques and technologies, which is as such not well-institutionalized in school mathematics.1

Rasch-Analysis

Roughly one half of 362 students from three German universities who participated in bridgingcourses (29% female) filled out test-form A before and test-form B after the courses. The other half took the opposite order. No sequence effects were found. Each participant received each test-form only once, and, although pre-and posttest samples were related (both samples consisted of the same participants), the occurrence of test-effects is not plausible. Using pre-and posttest samples in one analysis reduces the probability of the occurrence (respectively the effect) of a possible limitation of variance, which can lead to a possible underestimation of all correlational measures and possibly limiting the information value of assertions regarding validity. Participants were tested before and after a bridging course and therefore were not on the same performance level at both times of measurement.

To scale the data, we first estimated two onedimensional Rasch-models, one for each measurement point. A Rasch-model is a probabilistic psychometrical model for generating measurements from categorical data (e.g., right/wrong-answers in a performance test) as a function of the relation between the ability of the respondents and the item difficulty [START_REF] Rasch | Probabilistic models for some intelligence and attainment tests[END_REF]. EAP/PV-reliabilities were suitable, R = .868 (resp. .865 for Model 2), as well as the variances, V = 2.256 (resp. 1.967 for Model 2). Figure 2 shows the scatterplot of the rank of the difficulty parameters. Most importantly, the correlation of the difficulty parameters is high, R 2 = .95. For this reason, measurement invariance can be assumed.

Because of the high correlation between both measurement points, the approach of virtual cases could be applied (see Hartig & Kühnbach, 2005;[START_REF] Rost | Lehrbuch Testtheorie, Testkonstruktion [Textbook test theory, test construction[END_REF]. If a participant took part at both measurement points, he or she represents two cases in the data. This approach has two advantages: Firstly, resulting scores are in a consistent metric and secondly, the appearance of the problem of constrained variance is less likely (see above). With this approach, a data set of 724 cases resulted. Again, a one-dimensional model was calculated but also a three-dimensional model consisting of the three performance levels described before. Results are shown in Table 1. Both models show good variances and EAP/PV-reliabilities as well as discrimination indices.. The three-dimensional model shows significantly less deviance than the one-dimensional model (p < .001), so it fits the data better. 2 Figure 3 shows the wright-map of the three-dimensional model. Thus, the Raschanalysis empirically confirmed the three-dimensional structure of the test.

The order of tasks within the dimensions could be understood as a consequence of how intensively and how often (regarding different classes, schools etc.) the tasks are practiced; the order could hardly be deduced by theoretical considerations alone. In accordance with our content analysis, Dimension II in fact includes tasks which need conversions between different representations of a function, even if these tasks are not unfamiliar. The task in Figure 1 is even rated as a rather difficult one within Dimension II in the Rasch model. Within Dimension III, besides the degree of institutionalization and the time of treatment of indicated techniques in school,

2 One item (Item 3) shows a weighted MNSQ larger than 1.2 (values should lie in the range of 0.8 < MNSQ < 1.2). This is not too problematic for all other indices perform very well. the praxeological interconnectedness seems to be reflected in the order of tasks (items 3, 7, 10, 11, 12, 13, 15, 18, 20, 22). It is perhaps a little bit surprising that the complex term transformation task (item 13) turned out to be the most challenging task of Dimension III.

Discussion

The main aim of bridging courses is to support students by providing learning materials and samples of tasks for their self-evaluation. From the design of material and courses as well as the point of view of teaching, specific test instruments are required for a possibly objective evaluation of the impact of support measures. The test instruments should be most sensitive for specific mathematical knowledge domains and should allow relating pre-post-comparisons to specifics of bridging courses in order to adopt courses in view of actual pre-test results. Our results show that our test takes into account qualitatively different knowledge dimensions and might be a valuable tool for reaching these goals, which, of course, needs further investigations.

Figure 1 :Figure 2 :

 12 Figure 1: Example for a task of dimension II

Figure

  Figure 3: Wright-map of the 3D Rasch-model

Table 1 : Results of the Rasch-Analysis

 1

It should be noted that assigning tasks to a single of the dimensions is not always possible due to different possible solutions of a task. For the classification, several possible solutions were anticipated and the most probable one was used to determine the dimension. Analyses of some of our test tasks can be found in Feldt-Caesar (2017), which investigates validation issues.