Integrated Memory Grouping and Power-Aware MBIST Scheduling for MPSoCs

At this stage, we extract the physical parameters of each memory instance $m_i$ from layout information, such as DEF files, and construct a feature vector for clustering. Here, $m_i$ denotes the $i$-th memory instance, $C_i$ its clock domain, $T_i$ its memory type (SRAM macro type), $(x_i,y_i)$ the coordinates of the instance center in the layout, $A_i$ the cell area, $R_i$ the aspect ratio (e.g., $R_i=\log (w_i/h_i)$), and $P_i$ the power of the memory instance. From these physical continuous-valued quantities, we define the feature vector of memory $m_i$ as

The coordinates $(x_i,y_i)$, the area $A_i$, and the aspect ratio $R_i$ are standardized along each dimension to have zero mean and unit variance, so that none of these features dominates the distance computation excessively, and the relative weighting among position, area, and shape can be indirectly adjusted.

In addition, to preserve consistency in terms of clock domains and macro types, we first partition the set of memories into subsets for each combination $(C_i,T_i)$, and then independently apply DBSCAN and rectangular partitioning to each “clock domain $\times$ memory type” subset. As a result, the clustering process focuses on continuous position/area/shape information represented by $(x_i,y_i,A_i,R_i)$ rather than discrete labels such as clock domains and types, which leads to a region partitioning that more faithfully reflects the physical placement of memories.

Next, we describe our memory grouping method based on DBSCAN and rectangular partitioning.

We first summarize in Eq. (1) the local constraints that any pair of memories $(m_i,m_j)$ belonging to the same group ${𝒢}_k$ must satisfy.

Here, $m_i$ denotes the $i$-th memory instance. The attributes $m_i.\mathrm{clk}$ and $m_i.\mathrm{type}$ represent the clock domain $C_i$ and the memory type $T_i$, respectively. The coordinates $(x_i,y_i)$ denote the center of the instance in the layout, $a_i$ denotes the cell area, and $r_i$ denotes the aspect ratio. $P_m$ is the (relative) test power of memory $m$, and $D_{\max },N_{\max },A_{\mathrm{area}}^{\max },R_{\mathrm{aspect}}^{\max }$, and $P_{\text{group}}^{\max }$ are the thresholds for distance, maximum group size, area similarity, aspect-ratio similarity, and total power within a group, respectively.

We relate the grouping-stage power bound $P_{\text{group}}^{\max }$ to the chip-level instantaneous power limit $P_{\max }$ used in scheduling as follows. Since our scheduling targets activating up to $B_{\max }$ MBIST controllers in parallel, we set $P_{\text{group}}^{\max }$ so that even the worst-case concurrent execution of $B_{\max }$ groups stays within the chip-level budget:

In our experiments, we used $P_{\max }=4.0$ and $B_{\max }=2$, and thus set $P_{\text{group}}^{\max }=2.0$. This setting directly affects achievable parallelism and makespan: an excessively large $P_{\text{group}}^{\max }$ may allow high-power memories to concentrate in a few groups, creating bottlenecks that reduce effective utilization of the $B_{\max }$ parallel resources, whereas an excessively small $P_{\text{group}}^{\max }$ may over-fragment groups, increasing the number of tasks and potentially inflating scheduling overhead. Therefore, we use $B_{\max }{P}_{\text{group}}^{\max }\le P_{\max }$ as a practical guideline to balance per-group power while facilitating parallel execution during scheduling.

Conventional distance-based clustering methods rely solely on limited information, such as memory coordinates and types. They therefore cannot adequately reflect placement information, such as differences in size and shape. To address this issue, in this work, we construct a multidimensional feature space based on the continuous-valued features $(x_i,y_i,A_i,R_i)$ defined in the previous subsection and perform density-based clustering using DBSCAN in this space. This allows us to obtain initial clusters that simultaneously account for geometric proximity and similarity in area and aspect ratio.

In our method, memories labeled as noise in the standard DBSCAN output are relabeled as individual clusters, so that extremely isolated memories are retained as singleton groups. This post-processing yields a consistent initial clustering for both dense regions and isolated regions.

For neighborhood queries, we employ a spatial index structure (e.g., a $k$-d tree), which reduces the overall computational complexity of the DBSCAN phase to approximately $O(N\log N)$ [1] for $N$ memories. As a result, for each subset of memories with the same clock domain and macro type, those that are similar in area and shape are automatically grouped into the same cluster. In contrast, special memories placed in isolated regions are classified as independent clusters. In this way, the DBSCAN-based clustering can generate initial groupings that reflect physical placement and design characteristics, while remaining scalable even for large numbers of memories.

The initial clusters obtained by DBSCAN do not necessarily satisfy all test-related constraints summarized in Eq. (1). Therefore, for each cluster $G_j$, we recursively apply rectangular partitioning so that the following constraints in Eq. (1) become satisfied:

where $d(i,k)$ denotes the Euclidean distance between the centers of memories $i$ and $k$.

Algorithm 1 shows the pseudocode of the rectangular partitioning procedure. The function RectPartition first checks whether the current group $G$ already satisfies the above cardinality, distance, and power constraints; if so, it is returned as a single valid group. Otherwise, the bounding box of $G$ is computed and the region is split along its longer side. For each split ratio $r\in \{0.4,0.5,0.6\}$, the group is divided into two subgroups $(G_1,G_2)$ using Split, and RectPartition is applied recursively to each subgroup. For the resulting partition $P$, we consider it valid only if all groups satisfy the intra-group power constraint ${\sum }_{m\in G_j}{P}_m\le P_{\text{group}}^{\max }$. Among all valid candidates, we evaluate the cost

where $N_g$ is the number of generated groups and ${\sigma }_{\text{size}}$ is the relative standard deviation of group sizes, and select the partition with the minimum cost. By recursively repeating this process, we obtain rectangular memory groups that satisfy all constraints on group size, spatial extent, and total test power.

First, we estimate the test power and test time for each memory instance from the Liberty file of the corresponding SRAM macro. We take the average value of the entries in the internal power table as a relative test-power index for that macro, and assign this value to all instances of the same macro. In this way, we define the test power $P_i$ for each memory instance. The goal is not to obtain an accurate estimate of absolute power consumption, but rather to provide a relative measure that can be compared with the power limit introduced later.

For the test time, let ${\text{depth}}_i$ denote the number of words (depth) of memory $m_i$, $k_{\text{march}}$ the average number of accesses per word in the applied March test [26], and $f_{\text{test}}$ the MBIST test clock frequency in MHz. Then, denoting the required number of test cycles by $N_{\text{cyc},i}$ and the test clock period by $T_{\text{clk}}$, we approximate the test time $T_i$ as

By assigning the pair $(P_i,T_i)$ to each memory instance $m_i$, we obtain a task representation that is convenient for the subsequent scheduling algorithm.

For each memory group obtained by the rectangular partitioning, we assign one MBIST controller and denote the group IDs by $g=1,2,\mathrm{\dots },G$. Let $b(i)$ denote the group (BIST ID) to which memory $m_i$ belongs, and let $𝒯$ be the set of tasks. Then each task $i\in 𝒯$ is associated with the attributes $(P_i,T_i,b(i))$.

The scheduling problem considered here can be formulated as a Resource-Constrained Project Scheduling Problem (RCPSP) [9], where tasks are executed under two types of resource constraints, namely the test-power constraint and the MBIST-parallelism constraint, and the objective is to minimize the time until all tasks are completed. Let $𝒜(t)$ denote the set of tasks under test at time $t$. The power constraint can then be written as

where $P_{\max }$ is the maximum allowable test power, given as a design parameter reflecting, for example, the capacity of the power-distribution network.

We also assume that there exists an upper bound $B_{\max }$ on the number of distinct MBIST controllers (i.e., distinct BIST IDs) that can operate simultaneously, and impose the following parallel-BIST constraint:

Here, $B_{\max }$ denotes the maximum number of MBIST controllers that can be active simultaneously; in the experimental evaluation of this work, we set $B_{\max }=2$.

Each task is assumed to be non-preemptive and is executed continuously between its start time $S_i$ and completion time $C_i$. The objective function is to minimize the makespan, i.e., the maximum completion time over all tasks,

Since RCPSP is generally NP-hard, we do not pursue exact optimization in this work and instead apply a greedy heuristic described in the following subsection.

The proposed scheduler is implemented as an event-driven algorithm that alternates between two phases: (i) a phase in which all tasks that can be started at the current time $t$ are launched, and (ii) a phase in which, if no further task can be started, the time is advanced to the next task-completion event. Throughout the procedure, the algorithm maintains the sets of unscheduled and running tasks.

At each time $t$, the scheduler first computes the total test power consumed by the running tasks and the set of active BIST controllers, and derives the residual power from the remaining budget. It then extracts from the unscheduled tasks a candidate set consisting only of tasks that satisfy the following two conditions: (i) their test power fits within the residual power budget, and (ii) they either belong to a BIST controller that is already active, or activating a new BIST controller for them does not violate the parallel-BIST limit. The tasks in this candidate set are sorted in descending order of test time $T_i$ (and in descending order of power $P_i$ in case of ties), and are launched one by one following the LPT rule, while checking the power and BIST constraints.

If the candidate set becomes empty and no additional task can be started, the current time is advanced to the completion time of the earliest finishing task among the running tasks, and that task is removed from the set of running tasks. By repeating these “task-start” and “time-jump” steps until both the unscheduled and running task sets become empty, we obtain the start and completion times $(S_i,C_i)$ for all tasks as well as the final makespan $C_{\max }$. Considering the sorting of candidate sets and the number of events, the computational complexity is estimated to be on the order of $O(N^2\log N)$ with respect to the number of tasks $N$, which allows practical scheduling times even for SoCs with several hundred to several thousand memory instances.

The pseudocode of the proposed scheduler is shown in Algorithm 2.

Figure 2 shows an example of a schedule generated by the proposed scheduler for the first four MBIST controllers in a test case with 1,523 SRAM instances. The horizontal axis represents test time, and the vertical axis represents the total test power of the active memories at each time. Since power values express only relative relationships among memories, they have no physical units. Each color corresponds to a single MBIST controller. Under the maximum power budget of $P_{\max }=4.0$, the schedule satisfies the constraint that the instantaneous total test power never exceeds the upper limit. At the same time, the number of concurrently active MBIST controllers is kept no greater than $B_{\max }=2$ at any time.