Questions tagged [performance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
12 views

MAC protocol with throughput of 1

Consider a MAC protocol (ALOHA, CSMA, TDMA, etc.) that, even for very high loads, always results in a throughput of 1 (normalized with respect to the channel speed). Why is that not good if the ...
-1
votes
1answer
29 views

How to compute the max. speedup achievable of parallel program?

I was given the following problem to solve: Consider a system that has 128 compute units of the same type. Suppose that a program runs for 1025 time units on a single compute unit. The total amount ...
0
votes
1answer
22 views

MIPS pipeline: choosing between slowing down a stage and adding a new stage

Suppose a new, more complicated, instruction is desired for this simple pipelined MIPS processor. Suppose, also, it could be implemented by either (a) adding new logic to the execute stage of the ...
0
votes
1answer
22 views

Help with performance and speed-up question related to number of cores and their areas

There is a question in my exam that said: Consider the following three processors (x, y, and z) that are all of varying areas. Assume that the single-thread performance of a core increases with the ...
2
votes
1answer
25 views

Doubt on Performance Comparison of Splay Trees

I'm trying to understand splay tree performance compared to a standard balanced tree like AVL/red-black. In practice, I am pretty skeptical of the amortized bounds Tarjan and Sleator proves in their ...
0
votes
1answer
21 views

Average access time in two level cache system

In a two-level cache system, the level one cache has a hit time of 1 ns (inside the CPU), hit rate of 90%, and a miss penalty of 20 ns. The level two cache has a hit rate of 95% and a miss penalty of ...
3
votes
2answers
653 views

What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

This is a real-world application, not a student assignment. Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into ...
1
vote
2answers
25 views

Time efficient way to implement Multi-Armed-Bandits?

I'm doing a research on Multi-Armed Bandit (MAB) problem with approx. 1 million arms. In contrast, the number of iterations is of course much larger, about 10-20 million. Most MAB-algorithms require ...
0
votes
0answers
29 views

Amdahl's Law and efficient algorithms

Does the efficiency of algorithm leading to better performance of the system can be attributed to Amdahl's Law? or Is the Amdahl's law only applicable for the analysis of efficient hardwares and ...
0
votes
1answer
24 views

F-measure with $\beta > 1$

Consider the F-measure $F_{\beta}$. I know that with $\beta < 1$ precision is given more importance, ending with $F_{0} = precision$. With $\beta > 1$ means recall gets the upper hand, with the ...
0
votes
1answer
30 views

Performance speedup with Amdahl's law

Consider this question: A program has 1M instructions and 30% of them are SQRT with CPI=8. The CPI of the rest of the instructions are 3. If we reduce the CPI of SQRT to 2, how much speedup is ...
0
votes
0answers
30 views

How does database indexing improve performance for lookup?

I read that indexing a database will improve its performance by assigning a number to each row to loop through. Even after indexing, to get the data at say row 1024, shouldn't the memory reader go ...
0
votes
1answer
39 views

Classification accuracy based on top 3 most likely classifications

My goal is to recommend jobs to job seekers based on their skill set. Currently I'm using an SVM for this, which is outputting one prediction, e.g. "software engineer at Microsoft". However, consider ...
1
vote
1answer
28 views

Simplification of a multi-index Boolean expression towards computation in fewer steps

Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following ...
2
votes
2answers
44 views

Minimum words in a string given a dictionary

The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
0
votes
0answers
17 views

How to model internal queues shared between services in queueing networks

I am trying to model a load balancer as a queueing network. The load balancer has a number $n$ of internal threads. There is a central queue of requests from which the threads are fed. Each thread ...
1
vote
1answer
144 views

How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki "This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n ...
1
vote
1answer
47 views

Slowdown when accessing data at page boundaries?

Hi I have a program which accesses memory words that are located X bytes apart in virtual address space. For instance, ...
0
votes
2answers
29 views

How to properly compare performance of a prototype against a baseline

Assume that we have a baseline software B and a new prototype P that I want to compare with B. Ideally, I want to show that P performs some orders of magnitude or X times faster than B (on average). ...
-1
votes
2answers
948 views

Confusion in speed up calculation for pipeline architecture

This is an online question I am trying to solve. You are given a non-pipelined processor design which has a cycle time of 10ns and average CPI of 1.4.If a pipelined processor having 5 stages are 1ns, ...
1
vote
0answers
26 views

Can graph execution be better optimized than imperative programs?

I've been reading about Google's TensorFlow, and the way it represents calculations with graphs that are then executed by an engine. While the concept is interesting, I would like to understand why ...
0
votes
2answers
156 views

Importance of Frequency vs CAS Latency in memory performance

I was looking at the Wikipedia page for CAS Latency: https://en.wikipedia.org/wiki/CAS_latency And I noticed the obvious trend - at higher frequency, despite CAS latency degrading (growing), the ...
1
vote
1answer
93 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
3
votes
1answer
128 views

Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|). Now let's modify ...
3
votes
1answer
208 views

d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$. Then for a ...
1
vote
0answers
45 views

Accuracy and performance between a division and subtraction for a ratio in decibels

For comparing two images, one can use the Peak Signal-to-Noise Ratio (PSNR) metric, defined as follows: $\mathrm{PSNR} = 10 \cdot \log_{10}\left(\frac{\mathrm{MAX}^2}{\mathrm{MSE}}\right) = 20 \cdot \...
7
votes
1answer
153 views

Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?

Modern personal computers as far as I understand have increased in power (measured informally by ability to compute “more demanding programs”) due to two “broad factors”: decreased transistor size (...
2
votes
1answer
11k views

Cache effective access time calculation

In order to calculate the effective access time of a memory sub-system, I see some different approaches, a.k.a formulas. All are reasonable, but I don't know how they differ and what is the correct ...
3
votes
1answer
453 views

Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
1
vote
1answer
97 views

How to describe the time complexity of a continually running program with a stream of inputs?

Maybe time complexity isn't the right term. Performance? There must be some way of describing the efficiency of a program over time. For instance, I recently had a part of a program that took a ...
-1
votes
1answer
27 views

Performance - Computer Organization and design

A popular app takes 10 seconds to execute on a 11 watt smartphone A, and it takes 8 seconds to execute on a 13 watt smartphone B. The app is a bigger drain on the battery on which smartphone?
0
votes
1answer
38 views

How to show that i have significant improvements over the baselines?

I had review feedbacks regarding my recent publications and reviewers argued that the improvements are not significant over the baselines. I tried my classification algorithm on some image datasets ...
-1
votes
2answers
115 views

Big-O notation analysis [duplicate]

Can I get help to give an analysis of the running time Big-O? I'm not sure if all my answers are correct. I got for a) $ O(n)$, b) $O(n^3)$, c) $O(n^{1/2})$ and d) $O(log(n))$ ...
0
votes
1answer
92 views

Finding maximum clique in a distance matrix created by certain pattern

I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum ...
1
vote
0answers
61 views

Operation count: Solving Ax=b with sparse diagonal matrix

I've seen several tables that list operation counts for matrix-inversion related problems, but none of them actually brought forward the way of computing them. I'm interested in solving ...
0
votes
0answers
28 views

How to define a generic evaluation metric

Given a system (S) that accepts a tuple of parameters ($\alpha, \beta, \gamma \dots$ etc). These parameters affect the performance of S in a different way. For instance, decreasing $\alpha$ would ...
2
votes
1answer
815 views

Recursive functions from O(n) complexity to O(log n)

For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each ...
5
votes
1answer
2k views

Is Timsort more efficient than merge sort and why?

I was just wondering, I think merge sort is more efficient but not sure if that is true. I know it's to do with the complexities but am still struggling to understand.
1
vote
1answer
295 views

Trilinear interpolation for distorted cubes?

Is there a variation of trilinear interpolation that works on a "cube" that has been distorted (by moving one or more of its corners by an arbitrary amount into an arbitrary direction)? I know that I ...
0
votes
1answer
31 views

What do you call a lower/upper bound that is the best one?

I have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it ...
0
votes
0answers
146 views

Amdahl's Law when the speedup of new component = ∞

I was doing a problem about Amdahl's Law when I noticed that $s,(local$ $ speed-up)$ was incalculable. The wording: A computer takes 100 seconds to execute a program. The multiplication operations ...
3
votes
1answer
864 views

Variable size and CPU performance

When you learn programming they tell you choose data types that suffice for the concepts you're expressing, i.e. not too small because then your data won't fit and not too big because you don't want ...
1
vote
1answer
993 views

How to handle the repeat until convergence condition in time complexity and summarize the time complexity? [closed]

I am a novice in complexity calculation. I need to calculate the overall time complexity. My attempt is given below: Here, N = number of data points (N>300), C = ...
0
votes
0answers
127 views

Probability in Dynamic frame aloha

If I've RFID Collision Arbitration System that is based on multi-frame dynamic frame ALOHA. How can compute the probability of the average tag resolution $L_n$? ,$P_s$ is probability for packet ...
-1
votes
1answer
6k views

How do I calculate the speedup properly?

I am trying to calculate the speedup of this, but I am getting the wrong answer: Assuming that we have a program where we have two execution phases. One phase takes 1 time unit to execute and can ...
0
votes
1answer
43 views

Difference in scale between mean page loading times and exponentially distributed page loading times?

Apologies if this is the wrong place to ask. For my experiment, I have a single-page application and a multi-page application. I am testing them with an exponential distributed delay throttling. The ...
2
votes
2answers
212 views

Sorting networks hybrid sort

I saw an answer about the fastest way to sort an array with 6 elements. Turns out that using a sorting network is the best choice. If sorting networks are the fastest way to sort a small(< 16 ...
1
vote
2answers
64 views

Are fractions more computationally “expensive” than whole numbers?

I have a problem where the values are represented to humans as [0, .5, 1, ..., 8] But the function is massively recursive (game trees for a set of increasingly intractable problems) so I'm wondering ...
2
votes
1answer
172 views

What is the basic idea behind the usage of TLBs?

I know how Translation Lookaside Buffers work, and i also know we use them to improve the performance of data/program access by storing the recent page numbers - frame numbers in a memory cache. The ...
8
votes
2answers
359 views

GCD of a pair of products

I have two numbers, which are each the product of a large number of smaller numbers that I know. I want to find the GCD (Greatest common divisor) of these two numbers. Is there any way I can make use ...