Questions tagged [performance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
42 views

Interesting Speedup & Amdahl's law problem

I have found a problem on my Computer Architecture textbook which I have some issues with: We have a process which spends its time in the following way: 50% of the time, it executes common ...
0
votes
1answer
107 views

Metrics on which Clock Cycles Per Instruction(CPI) depends

In the book - Computer Organization and Design: The Hardware/Software Interface [RISC-V Edition] by Patterson and Hennessy, CPI is defined like this: The term clock cycles per instruction, which is ...
0
votes
1answer
24 views

Is it possible to generate a better random number generator algorithm from an algorithm that use N computers with one that uses N+1 computers?

Is it possible to generate a better random number generator algorithm from an algorithm that use N number of computers with an algorithm that uses N+1 number of computers? I use the word computer here,...
0
votes
0answers
18 views

What is the Memory Bandwidth Usage in a Program Related to?

We can use performance counter tools to check the memory bandwidth usage while a program is running. I want to ask what is this memory bandwidth related to? What parameters are involved in memory ...
0
votes
0answers
9 views

Throughput of slotted ALOHA when one node goes out of sync

What would be the throughput of slotted ALOHA when one node goes out of sync? Closer to ALOHA or slotted ALOHA? According to my calculations: For ALOHA we have probability of success = $N \cdot p \...
0
votes
1answer
63 views

Calculating CPU throughput on a single cycle vs multicycle datapath

When calculating the throughput of a CPU, how does it differ when it is implemented with a single cycle datapath versus a multicycle datapath? If for example the CPU is running 1 GHz freq, then ...
0
votes
0answers
16 views

what is instrument validation in computer science?

I'm writing an assignment involving some statistics comparing different implementation methods for web applications. I'll be using some downloaded software and web pages I create, on both virtualized ...
1
vote
0answers
54 views

Most scalable distributed consensus mechanism based on message complexity?

One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity. For example, PBFT message complexity is O(n^2) that ...
0
votes
0answers
18 views

The relationship between the capacity and the service rate

Assume a M/M/1 system is in it's steady state, given the capacity of the system is 200 req/sec at the maximum clock speed of 1 GHz, I'm confused how to get the service time for it? Does the capacity ...
1
vote
1answer
112 views

Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?

$$\log n+\log \frac{n}{2}+\log\frac{n}{4}+\log\frac{n}{8}+\cdots+\log\frac{n}{n}=\Theta (\log^2n).$$ The sum of logarithms is the logarithm of the product $n\cdot\frac{n}{2}\cdot\frac{n}{4}\cdot\frac{...
0
votes
1answer
15 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
47 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
31 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
33 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
56 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
479 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 ...
4
votes
2answers
1k 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
31 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
30 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
25 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
43 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
1answer
45 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
31 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
50 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 ...
1
vote
1answer
220 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
49 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
1k 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
31 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
529 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
112 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
3
votes
1answer
142 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
244 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
46 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
157 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 (...
3
votes
2answers
14k 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
1k 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
108 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
122 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
96 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
68 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
1k 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
3k 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
317 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
148 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 ...
5
votes
2answers
1k 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 ...